징검다리 건너기 - 프로그래머스 Level 3

문제 접근 방식

이 문제의 핵심은 "k 크기의 구간에서 최대값을 찾고, 그 최대값들 중 최소값을 찾는 것"입니다. 이는 다음과 같은 의미를 가집니다:

k 크기 구간의 최대값: 해당 구간을 건널 수 있는 최대 인원 수
모든 구간의 최대값들 중 최소값: 전체 징검다리를 건널 수 있는 최대 인원 수

해결 방법 - 최적화된 풀이

import collections

def solution(stones, k):
    if len(stones) == k:
        return sum(stones)
    d = collections.deque()
    res = float('inf')

    for ind in range(len(stones)):
        # 1. 현재 윈도우를 벗어난 값 제거
        while d and d[0] + k <= ind:
            d.popleft()

        # 2. 현재 값보다 작은 값들은 모두 제거
        while d and stones[d[-1]] < stones[ind]:
            d.pop()

        # 3. 현재 인덱스 추가
        d.append(ind)

        # 4. k-1 인덱스부터 결과값 갱신
        if ind >= k - 1:
            res = min(res, stones[d[0]])

    return res

코드 진행 과정 설명

예시를 통해 살펴보겠습니다.

stones = [2, 4, 5, 3, 2, 1, 4, 2, 5, 1]
k = 3

deque 초기화: 각 단계에서 현재 윈도우의 최대값 후보들의 인덱스를 저장
각 인덱스 순회하면서:
- 윈도우 크기(k) 유지를 위해 범위를 벗어난 인덱스 제거
- 현재 값보다 작은 값들을 가진 인덱스 제거 (이들은 절대 최대값이 될 수 없음)
- 현재 인덱스 추가
- k-1 인덱스부터는 현재 윈도우의 최대값(deque의 첫 번째 값)을 이용해 결과 갱신

시간 복잡도 분석

각 원소는 한 번만 deque에 들어가고 한 번만 나옵니다.
전체 시간 복잡도: O(n)

공간 복잡도 분석

deque의 크기는 최대 k를 넘지 않습니다.
전체 공간 복잡도: O(k)

주요 최적화 포인트

단조 감소 큐(Monotonic Queue) 활용
- deque를 사용해 윈도우 내 최대값들의 후보를 관리
- 항상 내림차순을 유지하여 최대값을 O(1)에 찾을 수 있음
불필요한 값 제거
- 윈도우를 벗어난 값들은 즉시 제거
- 현재 값보다 작은 이전 값들은 최대값이 될 수 없으므로 제거

코드 실행 예시

stones = [2, 4, 5, 3, 2, 1, 4, 2, 5, 1]
k = 3

위 예시에서:

첫 번째 윈도우 [2, 4, 5] -> 최대값 5
두 번째 윈도우 [4, 5, 3] -> 최대값 5
세 번째 윈도우 [5, 3, 2] -> 최대값 5
...

이런 식으로 각 윈도우의 최대값을 구하고, 그 중 최소값이 최종 답이 됩니다.

마무리

이 문제의 핵심은 "슬라이딩 윈도우의 최대값을 효율적으로 구하는 방법"입니다. Monotonic Queue를 활용하면 O(n)이라는 최적의 시간 복잡도로 문제를 해결할 수 있습니다.

마라민초닭발로제

[알고리즘] 징검다리 건너기 (프로그래머스)