836. Rectangle Overlap
축에 평행한 직사각형 두 개가 주어질 때, 교집합의 넓이가 양수인지 판단하는 문제. 변이나 꼭짓점만 닿는 것은 겹치지 않는 것으로 본다. easy지만 생각보다 easy하지 않은 문제. 처음엔 한쪽의 끝점이나 꼭짓점이 상대 직사각형 안에 들어가는지로 판단하려 했다. 그런데 한쪽이 다른 쪽을 품는 경우나 십자 모양으로 겹치는 경우를 놓치고, 경계 처리도 계속 …
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
easy 14
317 302 476. Number Complement
수가 주어질 때 complement를 구하는 문제. 1이 0이 되고 0이 1이 되려면?? XOR를 쓰면 된다. 자릿수를 올라가면서 1과 XOR를 하면 1은 0이 되고 0은 1이 된다.
295 860. Lemonade Change
5달러로 레모네이드를 팔 때 거스름돈을 줄 수 있는지 판단하는 문제. 손님은 5, 10, 20 달러 지폐만 사용한다. 그냥 단순 시뮬레이션. 약간의 그리디도 들어가는데 20달러를 냈을 때 10달러가 있다면 10달러 포함해서 거슬러 주는게 무조건 이득이다. 나머지는 5달러로 거슬러 주고 5달러 지폐가 음수가 되면 False를 리턴하면 된다.
292 703. Kth Largest Element in a Stream
stream이 주어질 때 순서대로 k번째로 큰 수를 출력하는 문제 min heap으로 간단히 구현할 수 있다. 처음에는 heap 2개를 썼는데 k개만 관리하면 돼서 k 길이의 min heap 하나면 충분하다. k 길이의 min heap을 관리하면서 min heap에서 가장 작은 값보다 큰 값이 들어오면 min heap에서 빼고 갱신해주면 된다.
276 2053. Kth Distinct String in an Array
문자열의 배열이 주어질 때 k번째 distinct한 문자열을 찾는 문제 그냥 Counter로 개수 세고 1개인 애들 중 k번째를 리턴하면 된다. easy 문제 풀면 자괴감 드네... (오늘의 문제니깐 푼다... ㅋㅋ)
273 1460. Make Two Arrays Equal by Reversing Subarrays
적당한 subarray를 골라서 swap했을 때 target 배열을 만들 수 있는지 체크하는 문제. 두 배열의 원소의 개수를 세서 같다면 만들 수 있다. 잘 생각해보면 버블 정렬 등 swap을 통해 어떠한 순서든 생성해낼 수 있다. swap의 횟수를 묻는 문제가 아니라 단순 True/False 문제이기 때문에 이런 식으로 간단하게 구할 수 있다. 비슷하게 …
255 231. Power of Two
n이 주어질 때 2의 제곱 (2^x) 인지 판단하는 문제. 단순 반복문은 너무 쉬우니 follow up 방식으로 해보자. 비트 연산을 쓰면 된다. 2의 제곱이라는 것은 비트로 나타냈을 때 ...0001000... 이런 꼴로 나오는 수인데 1을 뺐을 때 ...0000111... 처럼 1 자리 뒤가 전부 1로 바뀐다. 이 성질을 이용하면 n & (n - 1) …
249 2108. Find First Palindromic String in the Array
문자열의 배열 중에서 첫 번째 팰린드롬을 구하는 문제 말도 안되게 쉬워서 이걸 글을 써야 하나 싶지만... Daily 문제이기도 하고 지금까지 계속 썼기 때문에 일단 작성한다. 그냥 돌면서 팰린드롬인지 체크하면 된다.
248 169. Majority Element
배열에서 n / 2번 이상 나온 원소를 찾는 문제. (과반수 이상 나온 원소) 시간 O(n), 공간 O(n)이상의 솔루션은 매우 쉽다 (sorting, hashmap, 등등) 하지만 follow up 문제인 시간 O(n), 공간 O(1)은 꽤 어려운데... 이거는 Boyer-Moore Voting Algorithm을 써야 한다. 위대한 ChatGPT의 도움…
225 268. Missing Number
배열에서 0부터 n까지 수 중에 빠진 숫자를 구하는 문제. 그냥 배열 원소를 다 더한 후 0-n까지의 합에서 빼주면 된다. Easy 중에서도 쉬운 Easy. 디스커션 보니 XOR로도 풀었던데 그게 더 똑똑한 방법 같다 ()