85. Maximal Rectangle
2차원 배열에서 1로만 이루어진 가장 큰 직사각형의 넓이를 구하는 문제. 정사각형의 경우 간단한 DP로 가능한데 직사각형이므로 DP 풀이는 약간 복잡하다. 예전에 로이형 유튜브에서 보긴 해서 그 풀이로 가보기로 하자. 이전 문제인 84. Largest Rectangle in Histogram 문제를 응용하면 된다. 각 칸을 히스토그램의 칸이라 생각하고 아래…
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 165
174 173 224. Basic Calculator
괄호, +, - 가 있는 간단한 계산기를 만드는 문제. 스택으로 하면 될 것 같다. 기본 기호 (+, -) 가 나오면 스택에 집어넣고, 괄호가 나오면 새로 스택을 쌓아주고 괄호가 닫히면 스택에서 하나를 더 빼주는 식으로 구현했다. 약간 코드가 지저분하지만 기본 흐름은 스택을 쓰는 것이다.
172 149. Max Points on a Line
같은 직선에 있는 점의 최대 개수를 구하는 문제. 인풋 범위가 300개로 매우 작아서 그냥 다 돌려보면 된다. 심지어 x, y 범위도 작아서 (-10000 ~ 10000) 단순 기울기로만 카운트를 해주면 된다. 단, x, y 범위가 크다면 부동소수점 오차로 인해 gcd를 이용해서 기울기가 같은 점을 더해줘야 한다.
171 315. Count of Smaller Numbers After Self
배열에서 자신보다 뒤에 작은 수가 몇 개 나오는지 출력하는 문제. 처음엔 응?했지만 계속 보니 범위 문제라는 것이 보인다. 레드블랙트리에서 lower_bound 하거나 펜윅 트리를 쓰면 될 것 같다. 단, 레드 블랙 트리에서 lower_bound는 C++만 되는 것 같으니 간단한 펜윅 트리를 구현해보자. 위 링크에서 간략하게 핵심을 잘 정리해 놓았다. 범위…
170 295. Find Median from Data Stream
데이터 스트림에서 현재까지의 중앙값을 출력하는 문제. 이것도 꽤 유명한 문제라 딱 보고 우선순위 큐 2개로 푸는 것이 생각나긴 했다. 간단히 설명하자면 현재까지의 데이터를 두 덩어리로 나눈다. left, right로 나누고 left는 max heap, right는 min heap이다. 이를 이용하면 중앙값은 left, right 에서 얻어오는 값으로 바로 …
169 42. Trapping Rain Water
지도의 높이가 주어지고 비가 왔을 때 얼마나 찰 수 있는지 출력하는 문제. 물이 어떨 때 차는지 잘 살펴보면 된다. 물이 차는 높이는 현재 기준으로 왼쪽의 최대, 오른쪽의 최대 중 최솟값만큼 채워진다. 그렇다면 왼쪽의 최대, 오른쪽의 최대를 구하면 되는데 필요할 때마다 구하면 시간 초과가 되므로 미리 구해놓으면 된다.
168 239. Sliding Window Maximum
k 크기의 슬라이딩 윈도우에서 가장 큰 값들을 출력하는 문제. 말 그대로 슬라이딩 윈도우로 쭉 돌려가면서 큰 값이 될 후보를 덱으로 관리해주면 된다. 현재 값보다 작은 값이 이전에 나왔다면 그 값은 앞으로 최대가 될 수 없기 때문에 쭉 빼주는 연산만 해주면 된다.
167 4. Median of Two Sorted Arrays
두 정렬된 배열을 합쳤을 때의 중앙값을 구하는 문제. 이건 쉬워 보이는데 구현이 생각보다 빡세서 로이형의 도움을 많이 받았다. 먼저 기본적인 아이디어는 이진 탐색인데, 한 리스트를 잡고 그 리스트에 대해 이진 탐색을 진행하면서 중앙값을 찾는 방식이다. 한 리스트의 지점을 골랐다면 중앙값은 중앙에 있는 값이므로 다른 리스트의 지점도 자동으로 선택되는 걸 이용…
166 23. Merge k Sorted Lists
k개의 정렬된 리스트를 하나의 정렬된 리스트로 머지하는 문제. 간단한 해결책으로는 모든 리스트를 하나로 붙인 다음 정렬하는 것이다. 시간 복잡도는 O(N logN)이고 충분히 빨리 동작한다. 풀이를 보니 분할 정복 풀이가 정석인 것 같아서 분할 정복 스타일로 다시 풀었는데 이게 시간, 공간이 더 크다는?? 재귀 방식으로 풀었고 가운데를 잘라서 왼쪽 부분 오…
165 41. First Missing Positive
배열이 있을 때 배열에 나오지 않은 가장 작은 양의 정수를 구하는 문제. O(n) 으로 풀어야 하는데 생각보다 쉽지 않다. 키 포인트는 배열에 차례대로 자리가 있다고 생각하는 것이다. 즉, 1, 2, 3은 각각 배열의 0, 1, 2 인덱스에 차례로 들어 있어야 한다. 그러면 그 배열에서 nums[i] == i + 1이 되지 않는 처음 값이 나오지 않은 가장…