[C++] 11003 - 최솟값 찾기 (골드1)

1. 문제 설명

11003번: 최솟값 찾기

문제를 푸는 것보다 이해하는 데 더 오래 걸린 거 같다.

컴퓨터 언어만 파더니 한국어가 더 힘들어지나 보다....

---

2. 아이디어

 

다른 문제를 풀다가 아이디어를 참고하고 싶어 해결한 문제다 보니 이미 큐를 사용해야 하는 문제라는 걸 알고 있어서 쉽게 해결했다.

처음에는 queue로 문제를 해결하려 했지만, 자료구조 특성상 큐는 자료를 제거하는 쪽과 넣는 쪽이 각각 한 곳밖에 존재하지 않는다.

이 문제는 L이라는 값에 범위가 정해져 있기 때문에 단순히 값만 넣어서 될 것이 아니라 <위치, 값>으로 넣어야 한다.

값의 위치를 알면 i와 L로써 충분히 범위를 유추할 수 있기 때문에 범위를 오버하면 front 값을 pop한다.

최솟값보다 큰 값이 들어온다면 가장 뒤에 있는 값과 비교하여 처음부터 넣지 않으면 된다.

만약 현재 최솟값과 동일한 값이 들어오면 일단 넣고, 이전의 값이 유효 범위를 지나면 뒤의 값이 최솟값을 대신한다.

 

---

3. 코드

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;
typedef pair<int, int> pll;

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int N, L, t; cin >> N >> L;
    deque<pll> q;
    pll data;

    for (int i=1; i<=N; i++) {
        data.first = i; cin >> data.second;
        while (!q.empty() && data.second <= q.back().second)
            q.pop_back();
        q.push_back(data);
        if (q.front().first <= i-L)
            q.pop_front();
        cout << q.front().second << ' ';
    }

    return 0;
}