title: "[프로그래머스] 징검다리 건너기 Python 파이썬 해설 (Level 3) - 이도훈"
cleanUrl: "programmers/64062"
description: "프로그래머스 Level 3 문제 [징검다리 건너기]의 풀이를 정리합니다."

문제 설명 및 제한사항

아이디어 및 해결 방법

코드

from math import inf
from collections import deque

def solution(stones, k):
    # 배열 내의 k개의 연속된 자연수의 최댓값의 최솟값을 구하는 문제.
    # 
    # O(n)개의 sliding window 내의 최댓값을 단순히 max()로 구하면
    # 당연히 시간초과가 난다.
    # sliding window 내의 최댓값을 빠르게 구하는 방법이 필요하다.
    # 세그먼트 트리 써서 O(n x logn) 으로 풀 수도 있을 것 같은데, 해보자.
    # --> 세그먼트 트리도 시간초과가 난다. 그렇다면 O(n)에 하길 원하는 것 같다.
    #
    # 관리해야할 자료구조를 생각해보자. window 내의 maximum 값을 추적할 수 있어야 하고
    # window가 해당 값을 이탈하면 그 maximum 값을 삭제하고, 다음 maximum 값을 불러올 수 있어야 한다.
    # index 값들을 저장한 list (q) 하나를 가지고 이를 구현한다고 생각해보자.
    # 1. q 내의 인덱스 i에 대해 A[i]는 항상 내림차순으로 정렬되도록 i가 배열되어 있다.
    # ---> 즉, q[0]은 해당 window의 최댓값의 index이다.
    # 2. 새로운 인덱스 i를 본다고 하자. 그럼 현재 window는 i-k+1 ~ i 일 것.
    # 따라서 q[0]이 i-k+1보다 작으면 popleft해서 제거해야 한다.
    # 3. 또한 새로운 인덱스 i에 대해서 A[i]보다 작은 q[j]들을 pop해서 제거한 뒤 i를
    # q에 append한다.
    # 따라서 popleft, append, pop이 O(1)이면 좋으므로, deque를 쓰자.
    q, mn, i = deque(), inf, 0
    while i < len(stones):
        if len(q) > 0 and q[0] < i-k+1:
            q.popleft()
            
        while len(q) > 0 and stones[q[-1]] < stones[i]:
            q.pop()
        q.append(i)
        
        # 이제 stones[q[0]]은 i~i+k window의 최댓값을 가진다.
        # 적어도 k개의 숫자는 봐야 하므로, i가 k-1 이상일때부터 판단하면 된다.
        if i >= k-1 and stones[q[0]] < mn:
            mn = stones[q[0]]
        
        i += 1
        
    return mn

출처

프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges