백준 11003 최솟값 찾기 c++

문제 출처 : www.acmicpc.net/problem/11003

11003번: 최솟값 찾기

문제

N개의 수 A1, A2, ..., AN과 L이 주어진다.

Di= Ai-L+1~ Ai중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

입력

첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)

둘째 줄에는 N개의 수 Ai가 주어진다. (-109≤ Ai≤ 109)

출력

첫째 줄에 Di를 공백으로 구분하여 순서대로 출력한다.

알고리즘 분류

• 자료 구조
• 우선순위 큐
• 덱
• 슬라이딩 윈도우

풀이

시간제한에 유의하며 풀어야 하는 문제다.

첫 번째 코드는 입력 for문과 출력 for문을 따로 하여 시간 초과가 떴다.

두 번째 코드는 입력 for문에 출력도 같이 넣었으나 또 시간 초과가 떴다.

위 두 코드는 정답을 도출하는 priority_queue와 입력을 저장하는 자료구조

두 가지를 사용했으나,

세 번째 코드는 pair<int,int>를 저장하는 priority_queue 하나의 자료구조로

입력을 받고, 정답까지 도출했다.

priority_queue의 우선순위는 pair의 first부분을 기준으로 정렬된다.

큐의 second에는 index를 넣고, index가 start보다 작을 시 pop()해서

큐의 top에 start 부터 i까지의 최솟값을 유지시킨다.

코드1(시간 초과)

#include<iostream>
#include<queue>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(0);

    int n, l;
    cin >> n >> l;
    int *arr = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    for (int i = 1; i <= n; i++) {
        priority_queue<int,vector<int>,greater<int>> pq;
        int start =i - l + 1;
        for (; start <= i; start++) {
            if (start > 0) {
                pq.push(arr[start]);
            }
        }
        cout << pq.top() << ' ';
    }


    return 0;
}

코드2(시간 초과)

#include<iostream>
#include<queue>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(0);

    int n, l;
    cin >> n >> l;
    deque<int> dq;
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        priority_queue<int, vector<int>, greater<int>> pq;
        if (dq.empty()) {
            dq.push_front(a);
            pq.push(a);
        }
        else {
            if (dq.size() >= l) {
                dq.push_front(a);
                dq.pop_back();
            }
            else {
                dq.push_front(a);
            }
            for (auto x : dq) {
                pq.push(x);
            }
        }
        cout << pq.top()<< ' ';
    }



    return 0;
}

코드3(통과)

#include<iostream>
#include<queue>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(0);

    int n, l;
    cin >> n >> l;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;

    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        pq.push({ a, i });
        int start = i - l + 1;
        while (start > 0 && start > pq.top().second) {
            pq.pop();
        }
        cout << pq.top().first << ' ';

    }



    return 0;
}