42. Trapping Rain Water
지도의 높이가 주어지고 비가 왔을 때 얼마나 찰 수 있는지 출력하는 문제. 물이 어떨 때 차는지 잘 살펴보면 된다. 물이 차는 높이는 현재 기준으로 왼쪽의 최대, 오른쪽의 최대 중 최솟값만큼 채워진다. 그렇다면 왼쪽의 최대, 오른쪽의 최대를 구하면 되는데 필요할 때마다 구하면 시간 초과가 되므로 미리 구해놓으면 된다.
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
hard 68
169 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이 되지 않는 처음 값이 나오지 않은 가장…
164 65. Valid Number
문자열이 valid 한 수인지 판단하는 문제. 딱 보니 정규식으로 풀린다... 디버깅 시 위 사이트를 이용함. 문제에 나온 그대로 정규식으로 만들어주면 된다.
163 84. Largest Rectangle in Histogram
히스토그램이 있고 여기서 가장 큰 직사각형의 넓이를 구하는 문제. 이건 유명한 문제라 어떻게 보면 상식? 느낌. 스택을 쓰면 O(n)으로 풀 수 있다. 일단 키 포인트는 한 지점 까지의 최대 넓이를 구할 때 그보다 왼쪽에 큰 값이 있다면 그 큰 값은 무시된다는 것이다. 왜냐하면 현재 지점의 높이가 더 낮기 때문에 직사각형을 그렸을 때 포함되지 않기 때문이다…
161 32. Longest Valid Parentheses
괄호로 된 문자열이 주어지고 valid한 괄호 부분 문자열의 최대 길이를 구하는 문제. 딱 보니 스택이 생각난다. ( 괄호가 보이면 스택에 현재 인덱스를 넣고 ) 괄호가 보이면 스택에서 빼는 방식이다. 뺄 때 현재 인덱스에서 스택의 마지막 인덱스를 빼면 길이가 된다. 여기서 ()() 같이 서로 이어져야 되므로 스택은 기본적으로 1개의 원소가 들어가 있어야 …