python 11003 최솟값 찾기

📌 문제 정보

• 문제 번호: 11003
• 문제: https://www.acmicpc.net/problem/11003
• 난이도: 플래티넘5

---

🧩 문제 요약

수열이 주어졌을 때, 각 위치에서 **자기 앞 L개(포함)**를 보면서 최솟값을 구하는 문제.

• 수열 길이 N (1 ≤ N ≤ 5,000,000)
• 윈도우 크기 L (1 ≤ L ≤ N)
• 각 위치 i에 대해 i-L+1부터 i까지 중 최솟값을 출력
• 시간 제한이 매우 빡빡하므로 O(N log N)도 시간 초과 발생 가능
  → O(N) 알고리즘 필요

---

🧪 예제 입력 / 출력

 

입력

12 3

1 5 2 3 6 2 3 7 3 5 2 6

 

출력

1 1 1 2 2 2 2 2 3 3 2 2

 

설명:
슬라이딩 윈도우 범위 내 최솟값을 출력해야 함

• 앞에서 3개씩 묶어서 최솟값을 빠르게 찾아야 함

---

💡 접근 방식

• 슬라이딩 윈도우 방식 사용해야 함
• 윈도우 내부에서 최솟값만을 효율적으로 유지할 수 있어야 함
• 큐나 덱(deque)을 활용해 필요 없는 원소는 제거, 최소 원소만 남기기

---

⚙️ 알고리즘 설명

🔧 핵심 아이디어:
**덱(deque)**을 사용해서

1. 현재 값보다 큰 값은 뒤에서 제거
2. 범위를 벗어난 값은 앞에서 제거
3. 덱의 맨 앞에는 항상 최솟값이 위치

🔁 매 위치마다 다음을 수행:

• nums[i]보다 큰 값은 덱에서 제거 (뒤에서부터)
• (값, 인덱스) 형태로 현재 값 추가
• 가장 앞의 값이 윈도우 범위를 벗어나면 제거
• 덱의 앞에 있는 값이 현재 범위의 최솟값이므로 출력

---

🧑‍💻 코드 구현 (Python)

import sys
from collections import deque

input = sys.stdin.readline

N, L = map(int, input().split())
nums = list(map(int, input().split()))
q = deque()

for i in range(N):
    # 뒷부분에서 현재 값보다 큰 값은 제거
    while q and q[-1][0] > nums[i]:
        q.pop()
    
    # 현재 값 추가 (값, 인덱스)
    q.append((nums[i], i))
    
    # 윈도우 범위를 벗어난 값 제거
    if q[0][1] <= i - L:
        q.popleft()
    
    # 현재 윈도우의 최소값 출력
    print(q[0][0], end=' ')

---

🔁 다른 풀이 / 코드 개선 방향

• 우선순위 큐(min-heap)를 사용하는 방법도 있으나, 삭제 연산이 비효율적이라 시간 초과 발생
• 이 문제에서는 덱을 이용한 직접 관리 방식이 가장 효율적

---

⏱️ 시간복잡도 분석

• 시간복잡도: O(N)
  • 각 원소는 덱에 최대 1번 삽입, 1번 삭제되므로 총 O(N)
• 공간복잡도: O(N)
  • 입력 크기 및 덱에 들어가는 원소 최대 N개

---

📝 결론 및 팁

• 슬라이딩 윈도우 + 덱 패턴은 최솟값/최댓값 유지 문제에서 매우 자주 등장함
• 실전 코딩 테스트에서도 효율적인 최소값 구할 때 자주 사용되니 익숙해져야 함
• 이중 조건 (값 비교 + 인덱스 범위) 체크가 핵심 포인트

유사 문제 추천:

• 11001 수열 → https://www.acmicpc.net/problem/11001
• 15961 회전 초밥 → https://www.acmicpc.net/problem/15961
• 5430 AC → https://www.acmicpc.net/problem/5430