아이디어
어떻게 풀지?
한 사람이 완주할때마다 전체 원소들이 1씩 감소하는 것을 파악했으나 해결법이 떠오르지 않았다.
부분 리스트
그러다가 이 문제는 연속되는 k개 리스트의 최대값을 구하면 되는 것을 알아냈다.
문제 규칙 상 가장 가까운 디딤돌을 건너게 되어있다.
따라서 마지막 사람이 건너게 되면 리스트에 연속되는 k개의 0이 존재하게 된다.
즉, n - k + 1개의 부분 리스트들에 대해서 각각의 최대값들을 구한다.
그 중에서 가장 작은 값이 해답이 된다.
문제 예시로 보면 3, 2, 1에 대해 최대값이 3이고
이것이 부분 리스트들의 최대값 중에서 가장 작은 값이된다.
답은 알아냈는데
이 방법을 알고리즘으로 표현하는데 시간이 많이 걸렸다.
부분 리스트의 최대값은 순차적으로 구하면 시간 초과가 날 것이다.
순차적으로 구하면 O(NK) 시간 복잡도가 되기 때문이다.
이 시간 복잡도보다 빠른 방법이 뭐가 있을까하고 계속 생각했다.
그러다 우선순위큐가 좋은 자료구조가 될 수 있겠다고 생각했다.
코드의 주석 처리에 설명되어있다.
from heapq import heappush, heappop
def solution(stones, k):
# heap으로 최대값을 관리, Element: (-value, index)
# index outdated -> heappop
max_heap_with_index = []
for i in range(k):
heappush(max_heap_with_index, [-stones[i],i])
answer = -max_heap_with_index[0][0]
for i in range(k, len(stones)):
heappush(max_heap_with_index, [-stones[i],i])
# 현재 부분 리스트가 아닌 최대값은 힙에서 제거
while max_heap_with_index[0][1] < i - k + 1:
heappop(max_heap_with_index)
answer = min(answer,-max_heap_with_index[0][0])
return answer이런 방식으로 하면 힙에 원소 추가할 때 O(logN) 시간 복잡도이기 때문에
총 O(NlogN) 시간복잡도이니까 시간 초과 없이 답을 얻어낼 수 있을 것이다.
Road to..