오늘은 heap그리고 two pointer를 활용한 문제를 풀어보고자 한다. 이번엔 시간을 재고 풀어볼 것이다. 넉넉히 2시간을 잡았다.
Self 모의고사 문제
제한 시간: 2시간
내가 푸는데 걸린시간: 1시간 50분
- Last Stone Weight
https://leetcode.com/problems/last-stone-weight/
돌끼리 부딧혀서 마지막에 남는 돌이 뭔지 찾는 문제. Max-Heap으로 돌 정보를 쌓아두면서 처리하면 쉽게 풀린다. $O(NlogN)$
Beats: 6.67%
import heapq
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
stones = [-e for e in stones]
heapq.heapify(stones)
diff = 0
while stones:
largest = heapq.heappop(stones)
if not stones:
return -largest
second = heapq.heappop(stones)
diff = largest - second
if diff == 0:
continue
else:
heapq.heappush(stones, diff)
return -diff
- Task Scheduler
https://leetcode.com/problems/task-scheduler/
Beats: 5.1%
이 문제가 가장 까다로운 문제였고 거의 1시간 좀 넘는 시간을 이 문제에 투자했다.
2개의 HashMap으로 정보를 트래킹하고, Heap으로 처리 가능한 task를 트래킹하면서 정답을 추가한다. 전체 element 수를 N, task 갯수가 T개 라고하면 O(NlogT) 알고리즘. 여기서 cooldown의 key갯수는 $k$개인데 이건 무시.
문제를 잘보면, 아이디어는 동일한 task가 많은 task가 우선순위로 처리되어야 한다는 점을 알 수 있다. 그래서 task $T$개에 대해 처리해야한 동일한 테스크 양을 key로 갖도록 Max-Heap을 관리한다. 그런데, 까다로운 조건이 cooldown 시간인 n 값이 주어져서 Max-Heap에 들어갈 타이밍을 cooldown HashMap으로 트래킹하면서 집어넣어야한다. 그리고 모든 task가 끝나는걸 또 트래킹하기 위해 또다른 HashMap으로 pending을 통해 테스크에 대한 정보를 관리한다. 이것이 필요한 이유는 Heap에 존재하는 Task만 CPU가 처리할 수 있도록 하기 때문에 Heap에서 나온 Task에 대한 정보를 따로 저장해놓을 pending 같은 HashMap이 필요해서이다.
import heapq
from collections import Counter
class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
cooldown = {}
tasks = [(-cnt, task) for task, cnt in Counter(tasks).items()]
pending = {e[1]: e[0] for e in tasks}
heapq.heapify(tasks)
ans = []
while not all(e >= 0 for e in pending.values()):
if tasks:
task_cnt, task_prty = heapq.heappop(tasks)
pending[task_prty] = task_cnt + 1
cooldown[task_prty] = n
else:
task_prty = "idle"
ans.append(task_prty)
# TODO - cooldown: set, and down all related task
possible_tasks = []
for t in cooldown.keys():
if task_prty != t:
cooldown[t] -= 1
if cooldown[t] == 0 and pending[t] < 0:
possible_tasks.append(t)
for t in possible_tasks:
del cooldown[t]
heapq.heappush(tasks, (pending[t], t))
# print(ans)
return len(ans)그런데, 굳이 Heap으로 하나씩 해보지 않아도 답안의 원리를 꺠달으면 수식화해서 구할 수 있다.
여기 설명이 잘되어있다.
결론을 말하면 이렇게 계산할 수 있다. (mx-1)*(n+1)+x
여기서 x는 task중 동일한 테스크가 최대인 것(겹친다면 그들) 수, mx는 동일한 테스크의 최대 수 이다.
따라서, 다음과 같이 풀면 된다.
class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
cnt = [0] * 26
for i in tasks: cnt[ord(i) - ord('A')] += 1
mx, mxcnt = max(cnt), 0
for i in cnt:
if i == mx: mxcnt += 1
return max((mx - 1) * (n + 1) + mxcnt, len(tasks))까다로운 조건하 Heap을 사용해보는 연습을 하기엔 처음 접근법이 꽤나 도움이 되었다.
- Container With Most Water
https://leetcode.com/problems/container-with-most-water/
이 문제는 처음에는 보자마자 쉽게 생각하고 풀었다가 TLE로 당황해서 여러 접근법을 다 시도해보고나서야 효율적인 알고리즘을 찾았다.
가장 쉬운 방법은 모든 pair들을 골라보고 최대가 되는 정답을 찾는 방법이다.
$O(N^2)$: TLE
from math import fabs
class Solution:
def maxArea(self, height: List[int]) -> int:
n = len(height)
ans = 0
for i in range(n):
for j in range(n):
ans = max(ans, int(fabs(i - j)) * min(height[i], height[j]))
return ans한 걸음 더 나아가 개선할 방법을 고민하던 차 Maxium subarray 문제랑 비슷한것 같아 Divide conquer 접근법을 사용했다.
$$
T(N) = 2(T/2) + O(N) = O(NlogN)
$$
하지만 이 방법 역시도 TLE.
from math import fabs
class Solution:
def maxArea(self, height: List[int]) -> int:
def dc(s, e):
if e == s:
return 0
elif e - s == 1:
return min(height[s], height[e])
mid = (s + e) // 2
left = dc(s, mid)
right = dc(mid + 1, e)
merged = 0
for i in range(s, mid + 1):
for j in range(mid + 1, e + 1):
merged = max(merged, int(fabs(i - j)) * min(height[i], height[j]))
return max(left, right, merged)
return dc(0, len(height) - 1)곰곰히 생각해보니 Tow pointer 접근법으로 $O(N)$ 에 풀 수 있었다. 가장 끝쪽의 왼쪽, 오른쪽에서 높이가 높은 기둥이 있다면 멈추고 반대편의 포인터를 변화시켜가며 두 포인터가 만날때까지 최대값을 찾으면 된다.
내가 문제를 풀때는 어렴풋이 감각으로 한쪽이 높으면 반대편을 이동시키면 될 것 같다고 생각하고 풀었긴 했는데, 원리를 이해하고 풀진 못했다.
이렇게 풀 수 있는 이유는 여기서 잘 설명하는데, 다음 한 문장이 핵심 문장이다. 이 문장이 왜 그런지 이 글을 쓰신 분이 유튜브에 자세한 설명을 올려놓았다.
The key insight here is that moving the longer side inwards is completely unnecessary because the height of the water is bounded by the shorter side
Beats: 25.12%
class Solution:
def maxArea(self, height: List[int]) -> int:
i, j = 0, len(height) - 1
ans = 0
while i < j:
ans = max(ans, (j - i) * min(height[i], height[j]))
if height[i] < height[j]:
i += 1
else:
j -= 1
return ans총평
오늘은 heap 사용과 two pointer를 활용한 문제를 풀어보았다. 자주 출제되는 유형인 것 같고 Two pointer를 사용할 수 있었던 것은 문제에 숨겨진 강력한 핵심 전제를 찾아내는게 관건이었다.