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