[백준] 11003번 : 최솟값 찾기

---

🔗 문제 링크

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

---

반응형

728x90

👩‍💻 코드

#include <iostream>
#include <deque>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N, L;
    cin >> N >> L;
    
    deque<pair<int, int>> dq;
    for (int i = 0; i < N; i++) {
        int n;
        cin >> n;
        
        if (!dq.empty() && dq.front().second <= i - L) {
            dq.pop_front();
        }
        
        while (!dq.empty() && dq.back().first > n) {
            dq.pop_back();
        }
        
        dq.push_back({n, i});
        
        cout << dq.front().first << " ";
    }

    return 0;
}

---

📝 풀이

Do it! 알고리즘 코딩테스 - C++ 편 : 기출 유형 분석부터 문제 풀이 비법까지!를 참고하였습니다.

 

deque에는 (값, 인덱스) 형태로 저장합니다.

 

만약 deque의 front의 인덱스가 슬라이딩 윈도우 범위를 벗어난다면 제거합니다.

deque의 back의 값이 입력 받은 수보다 크다면 제거합니다.

 

이 과정을 통해 deque의 front에는 항상 최솟값이 유지됩니다.

따라서 deque의 front값을 출력해주면 됩니다.