[프로그래머스: Python] 64062 - 징검다리 건너기

https://school.programmers.co.kr/learn/courses/30/lessons/64062

프로그래머스

 

어려웠습니다. 2개의 알고리즘을 혼합해서 사용하는 것에 익숙하지 않아서 애를 먹었습니다.

 

문제를 보면 stones의 길이가 20만이기 때문에 부르트포스로는 풀 수 없다는 것을 알 수 있습니다. 그렇기 때문에 이를 선형 시간이나 로그 시간 안에 풀어내야 합니다.

 

문제의 핵심은 얼마나 많은 사람을 건너게 할 수 있느냐인데, 이를 확인하는 방법은 연속된 k개의 돌 중, 내구도가 최대 중에 최소인 돌을 찾는 것입니다.

 

연속된 k개를 보는 이유는 특정 위치에서 점프했을 때 도달할 수 있는 경우의 수를 보는 것입니다. 그중에서 최대를 찾는 이유는, 점프가 가능한 범위 내 다른 돌들이 건널 수 없는 상황에서 유일하게 살아있을 가능성이 있기 때문입니다.

---

[풀이[

k가 3인 기본 케이스에 대해 보겠습니다.

[2, 4, 5]	5
[4, 5, 3]	5
[5, 3, 2]	5
[3, 2, 1]	3
[2, 1, 4]	4
[1, 4, 2]	4
[4, 2, 5]	5
[2, 5, 1]	5

위 예시를 보면 첫 슬라이딩 윈도우에서 네 번째 사람이 와도 마지막 블록은 살아있습니다. 즉 2가 없으면 4, 4가 없으면 5까지 이동시킬 수 있다는 것이죠.

 

첫 돌을 밟았다고 했을 때도 마찬가지입니다. 4, 5, 3을 밟을 수 있지만, 그중에서 많은 사람들을 옮길 가능성이 있는 것은 5입니다.

 

이러한 흐름을 반복하며 다음으로 k이내로 이동할 수 있는 지점들 중, 많은 사람들을 옮길 수 있는 돌을 선택합니다. 그리고 그러한 값 중 최소를 찾아내면 정답이 됩니다.

 

왜냐하면 내구도가 최소인 돌이 가장 먼저 부서질 것이고, 그렇게 되면 다음 돌들로 이동할 수 없기 때문입니다.

---

[전체 코드]

import heapq

def solution(stones, k):
    answer = max(stones) + 1
    heap = []
    
    for i in range(k - 1):  # 다음 탐색에서 값을 바로 추가하므로 k - 1개만 저장
        heapq.heappush(heap, (-stones[i], i))
        
    for i in range(k - 1, len(stones)):
        heapq.heappush(heap, (-stones[i], i))  # 윈도우에서 매번 max를 하지 않기 위해 heap 사용
        while heap and heap[0][1] < i - k + 1:  # 슬라이딩 윈도우 유지
            heapq.heappop(heap)
        answer = min(answer, -heap[0][0])
    
    return answer

최댓값을 찾기 위해 힙을 쓰는 이유는, 잘라낸 윈도에 max 연산을 하게 되면 매번 k번의 연산이 발생하기 때문입니다.