문제 바로가기

효율성 테스트가 존재하므로 완전 탐색으로는 풀 수가 없는 문제입니다. 대부분의 블로그에서 binary search를 이용한 $O(n\log n)$ 의 방법만 설명되어 있길래, 슬라이딩 윈도우를 이용한 $O(n)$ 의 풀이방법을 올려봅니다.

풀이 방법 (슬라이딩 윈도우)

---

친구들을 계속 건너게 했을 때, 연속해서 k개의 숫자가 0인 징검다리가 나오는 순간을 포착하면 된다.

이는
길이가 k인 모든 부분 수열에 대해, 부분 수열의 max값이 가장 작은 부분 수열을 찾는 것 과 동일하다. 어떤 징검다리들이 가장 먼저 0이 될지를 생각해보면 이해할 수 있다.

[2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 에 대해서 가져와보면,
k = 3 인 부분 수열은
[2, 4, 5], [4, 5, 3], ,,,, [2, 5, 1] 이렇게 있다. 이들의 최댓값중 가장 작은 최댓값은
[3, 2, 1] 일 때, 3으로 존재한다. 따라서 3을 return 하면 정답이다.

---

이걸 슬라이딩 윈도우를 이용하면 $O(n)$으로 해결할 수 있다. 해당 window에 대해서 deque을 내림차순이 되도록 원소들을 선택해, 맨 앞에 있는 원소가 항상 최댓값이 되도록 구현하면 된다.

글로만 보면 이해가 힘들다. 아래 그림을 보자.

• 첫번째 줄을 보면 [2, 4, 5]가 현재 window에 포함된 숫자들이고, 이 때의 최댓값은 5이다. 2와 4는 5보다 작고, 5보다 먼저 window에서 빠져나가기 때문에, 어떠한 window에 대해서도 최댓값이 될 수 없다. 따라서 현재 deque에는 2와 4는 담지 않고, 5만 담는다.

• 두번째 줄을 보자. 현재 window는 [4, 5, 3] 이고, 위에서 설명했듯이 4는 고려할 필요가 없다. 3의 경우는 5보다 작긴 하지만, 5가 window에서 빠져 나간 경우 (4번째 줄 같은 경우) 최댓값이 될 수도 있으므로 deque에 넣어놓는다.

• 세번째, 네번째 줄에서는 마찬가지 이유로 2와 1을 뒤에 넣어주면 된다. 네번째 줄에서는 5가 빠져나간다.

• 다섯번째 줄이 유의할 점인데 기존에 존재하던 2, 1보다 4가 더 크고, 뒤에 나왔다. 첫번째 줄에서 설명했던 것과 정확히 동일한 현상인데, 따라서 2와 1을 pop하고 4를 넣어준다.

즉, 이러한 일련의 과정에서 deque의 가장 앞 원소가 항상 그 window에서의 최댓값이 되고, 모든 부분 수열에 대해서 $O(n)$으로 계산을 할 수 있다.

---

구현은 아래와 같다. 윈도우 왼쪽에서 popleft되는 경우를 위해 deque에 직접적인 값이 아닌 index를 집어넣었다.

from collections import deque

# max가 가장 작은, 길이가 k인 부분 수열을 뽑으면 된다.
# 이 때, 그 부분 수열에서의 최댓값이 답.

# 슬라이딩 윈도우 활용
def solution(stones, k):
    n = len(stones)
    deque_k = deque()
    deque_k.append(0)
    
    for i in range(1, k):
        # 뒤쪽에 필요 없는 애들 다 제거
        while deque_k and stones[deque_k[-1]] < stones[i]:
            deque_k.pop()
        
        # 비었거나, 값이 더 큰 경우에만 집어넣기
        if not deque_k or stones[deque_k[-1]] >= stones[i]:
            deque_k.append(i)
    
    answer = stones[deque_k[0]]
    
    for i in range(k, n):
        # 뒤쪽 제거
        while deque_k and stones[deque_k[-1]] < stones[i]:
            deque_k.pop()
        
        # 앞쪽 제거
        while deque_k and deque_k[0] <= i - k:
            deque_k.popleft()
        
        # 더 큰 경우에만 집어넣기
        if not deque_k or stones[deque_k[-1]] >= stones[i]:
            deque_k.append(i)
        
        answer = min(answer, stones[deque_k[0]])
    return answer