[프로그래머스] - 징검다리 건너기 (LEVEL3)

programmers.co.kr/learn/courses/30/lessons/64062

코딩테스트 연습 - 징검다리 건너기

구간의 최댓값을 구하는 문제

 

index를 1씩 증가시키면서 max 값을 하나하나 다 구하면 효율성 테스트를 통과하지 못한다.

 

그래서 찾아보니 sliding window maximum 알고리즘이 있었다.

 

일정 구간 속에서 index를 증가시키며 max값을 효율적(O(n))으로 탐색하는 방법이다.

 

Sliding Window Maximum

 data = [1, 2, 3, 2, 1],    k = 3 이라고 할 때,

data의 연속된 k개의 값의 max 값을 찾기 위해서, 우리는 [1, 2, 3], [2, 3, 2], [3, 2, 1] 각각의 k개의 값을 비교해서 최댓값을 구하는데 그럴 필요가 없다.

왜냐하면 [2, 3, 2]의 최댓값을 구할 때, 앞구간( [1, 2, 3] )에서 [2]는 이미 최댓값이 될 수 없으므로 다시 한번 더 비교할 필요가 없는 것이다.

 

 Sliding Window Maximum 알고리즘은 이를 바탕으로 한 것으로, queue를 이용해 구현한다.

k개의 구간 속 max값을 찾는다고 할 때, 기본적인 방식은 다음과 같다.

 

1) Window 크기를 유지하기 위해, (current_index) - queue[0] 의 값이 k 이상이면 popleft()

 

2) queue가 비어있지 않으면, data[current_index] 가 data[queue[-1]] 보다 클 때까지 pop()

    = data[current_index] 보다 작은 값은 모두 지움, max값의 후보들만 남긴다.

 

3) queue에 current_index를 append

 

4) 해당 Window의  max값은 data[queue[0]]

 

<My Solution>

from collections import deque
def solution(stones, k):
    answer = 200000001
    q = deque()
    for i in range(k):
        while q and stones[i]>=stones[q[-1]]: q.pop()
        q.append(i)
    answer = min(answer,stones[q[0]])
    for i in range(k,len(stones)):
        while q and q[0] <= i-k: q.popleft()
        while q and stones[i]>=stones[q[-1]]: q.pop()
        q.append(i)
        answer = min(stones[q[0]],answer)
    return answer