[백준 파이썬] #11003. 최솟값 찾기

풀기 전 생각해보기😮

• 정렬을 사용할 수 없음 : 최대범위 값이 너무 크다
• 슬라이딩 윈도우, 덱 자료구조를 이용해서 O(n) 시간복잡도로 풀기

---

풀이🛫

from collections import deque

N, L = map(int, input().split())
arr = list(map(int, input().split()))
myDeque = deque()

# ([인덱스][값]) 형태로 myDeque에 데이터 관리
for i in range(N):

    # 새로운 값이 기존의 값보다 클 때까지 기존의 값 (끝에서부터) 제거
    while myDeque and myDeque[-1][0] > arr[i]:
        myDeque.pop()
    myDeque.append((arr[i], i))     # 새로운 값 입력

    # 슬라이딩 윈도우가 인덱스 범위에서 벗어난 경우 제거
    if myDeque[0][1] <= i-L:
        myDeque.popleft()

    print(myDeque[0][0], end=' ')

 

✅ 문제 분석

• 윈도우의 크기는 최솟값을 구하는 범위가 i-L+1 ~ i까지이므로 L로 생각
• N, L의 최대범위가 5,000,000이므로 정렬을 사용할 수 없음

⇒ O(N) 시간복잡도로 해결 : 슬라이딩 윈도우를 덱 구조를 사용해서 사용

※ 덱을 사용해서 정렬 효과를 보는 방법 풀이 😃 (p.73 참고)

• 인덱스와 값을 저장
• 새로운 값이 들어올 때, 뒤에서부터 값을 비교
  • 값이 기존에 있던 값보다 클 경우, 그대로 추가
  • 값이 기존에 있던 값보다 작을 경우
    • 새로운 값이 기존의 값보다 클 때까지 기존의 값 제거
  ⇒ 오름차순으로 정렬되는 효과를 볼 수 있다
• 최소값은 윈도우 범위 내에서 찾아야 하는 조건을 적용했을 때, 덱 구조에서 가장 앞에 있는 값이 최소 값이 된다

 

링크💎

https://www.acmicpc.net/problem/11003

11003번: 최솟값 찾기