[프로그래머스] / [Level 3] / [Python] 징검다리 건너기

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

프로그래머스

---

슬라이딩 윈도우 방식을 사용하여 범위 k개의 내의 리스트 중 최대값을 구하고 그 최대값들 중 최소값을 구하면 된다.

def solution(stones, k):
    answer = []
    
    for idx in range(0, len(stones) - k + 1):
        answer.append(max(stones[idx:idx+k]))
        
    return min(answer)

하지만, 효율성 테스트에서 통과하지 못하였다. 이유를 생각하였을 때, 매번 k 범위 내에서 최대값을 구하는 부분에서 많은 비용이 필요하다는 것을 알 수 있었다.

이를 해결하기 위해 일정 범위 내의 최대값을 계속해서 업데이트하는 방식을 생각하였고 이를 큐를 사용하여 해결하였다.

from collections import deque

def solution(stones, k):
    answer = float('inf')
    q = deque()    

    for idx, stone in enumerate(stones):
        while q and stones[q[-1]] < stone:
            q.pop()      
        q.append(idx)
        
        # 범위 조절
        if q[0] == idx - k:
            q.popleft()
        
        # 현재 idx 까지의 최대값들 중 최소값
        if idx >= k - 1:
            answer = min(answer, stones[q[0]])

    return answer