11003번: 최솟값 찾기 (BOJ C/C++)

11003번: 회전하는 큐

사용 언어: C++

 

문제

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를 공백으로 구분하여 순서대로 출력한다.

 

첫 번째 풀이 (덱)

#include <iostream>
#include <deque>
#define MAX 5000000
using namespace std;

int arr[MAX];
deque<pair<int, int>> dq;

int main(void)
{
        ios::sync_with_stdio(0);
        cin.tie(0);

        int N, L;
        cin >> N >> L;

        for(int i=0; i < N; i++)
                 cin >> arr[i];

        for(int i=0; i < N; i++)
        {
                 //안 비어있고 dq에 L개보다 넘치면 pop_front
                 if (!dq.empty() && i - L == dq.front().second)
                         dq.pop_front();

                 //dq에 arr[i]보다 큰 수는 더 이상 쓸 일 X -> pop_back 
                 while (!dq.empty() && dq.back().first > arr[i])
                         dq.pop_back();

                 dq.push_back({arr[i], i});
                 cout << dq.front().first << " ";
        }
        cout << "\n";

        return 0;
}

 

두 번째 풀이 (우선순위 큐)

#include<iostream>
#include<queue>

using namespace std;

struct cmp
{
    bool operator()(const pair<int,int>& a, const pair<int,int>& b)
        {
            return (a.first > b.first); 
        }
};

int main(void) 
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, L;
    cin >> N >> L;
    //priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
    priority_queue<pair<int,int>,vector<pair<int,int>>, cmp> pq;

    for (int i = 0; i < N; i++)
    {
        int num;
        cin >> num;
        pq.push({num, i});

        //안 비어있고 pq에 L개보다 넘치면 pop_front
        while (i - L + 1 > 0 && i - L + 1 > pq.top().second)
            pq.pop();

        cout << pq.top().first << ' ';
    }
    cout<<'\n';

    return 0;
}

위 코드에서 priority_queue를 정의할 때 cmp 함수를 썼지만 훨씬 간단하게 바꿀 수 있다. 큐 헤더에서 제공하는 greater을 써서 greater<pair<int,int>>로 바꾸면 아래처럼 cmp 함수 없이도 코드를 많이 줄일 수 있다.

priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;