[우선순위 큐] 최솟값 or 최댓값 찾기 알고리즘(feat. deque)

 

 

최솟값, 최댓값 찾기 문제에서 정렬을 사용할 수 없다면, 우선순위 큐를 생각하세요

 

들어가며

시간복잡도를 측정하는 문제 중에서는 까다로운 문제들이 많습니다. 특히 정렬이 필요한 경우인데, 정렬은 기본적으로 NlogN의 시간복잡도를 가집니다. 특정 문제의 요구사항에서는 적어도 N의 시간복잡도를 요구하는 부분이 있습니다. 이럴 땐 우선순위 큐를 사용하면 logN의 시간복잡도를 가질 수 있습니다.

 

문제

백준 11003

 

처음에는 문제 자체가 이해되지 않았습니다. 슬라이딩 윈도우 형태로 고정된 구간이 이동하면서 그 중 최소값을 찾는 문제더라구요. N의 최대 범위가 5,000,000이므로 정렬을 사용하게 되면 시간초과입니다.

저는 문제를 두가지 파트로 나눴습니다. 첫 번째는 구간이 이동함에 따라 최소값 리스트를 갱신해주는 작업, 두 번째는 구간이 이동함에 따라 기존 최소값을 버리는 작업입니다. 우선순위 큐와 덱(deque)을 사용하여 두 가지 방법으로 풀어보겠습니다. 문제의 핵심은 정렬 알고리즘을 사용하지 않고도 정렬효과를 보는 것입니다.

 

풀이1(우선순위 큐)

우선순위 큐는 힙을 사용하여 내가 설정한 기준에 맞게 자동으로 정렬되면서 자료구조에 배치됩니다. 따라서 최소값 리스트를 갱신해주는 작업은 자동으로 되며, 슬라이딩 윈도우가 이동함에 따른 기존 최소값 버리는 작업만 구현해주면 됩니다.

알고리즘
1. 인덱스와 값을 갖는 Item 데이터 만들고, 최소값 우선순위 큐를 생성
2. N만큼 순회하면서 값을 큐에 넣고, 현재 큐 최소값의 인덱스가 슬라이딩 윈도우를 벗어나면 삭제
3. 큐의 최솟값 출력

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Item {
    int index;
    int value;

    bool operator<(const Item& other) const {
        return value > other.value; // 작은 priority가 top에
    }
};

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int N, L;
    cin >> N >> L;

    priority_queue<Item> pq;

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

        auto currentMinItem = pq.top();
        const int start = i - L + 1;
        while (currentMinItem.index < start)
        {
            pq.pop();
            currentMinItem = pq.top();
        }

        printf("%d ", currentMinItem.value);
    }
}

 

풀이2(deque)

덱은 양방향으로 push와 pop이 되는 구조입니다. 덱으로도 최솟값 리스트를 정렬하면서 슬라이딩 윈도우를 구현할 수 있습니다.

알고리즘
1. N만큼 순회하면서 덱의 맨 끝 값이 현재 값보다 크면 맨 끝 값 제거(덱의 처음 부분이 최솟값)
2. 현재 값 덱의 끝으로 삽입
3. 현재 덱의 맨 앞 데이터(최솟값 데이터)가 슬라이딩 윈도우를 벗어나면 제거
4. 덱의 맨 앞 데이터 출력

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int N, L;
    cin >> N >> L;
    deque<pair<int,int>> dq;	// idx, value

    int num;
    for (int i = 0; i < N; i++)
    {
        cin >> num;

        while (!dq.empty() && dq.back().second > num)
        {
            dq.pop_back();
        }

        dq.push_back({ i, num });

        const int start = i - L + 1;
        if (dq.front().first < start)
            dq.pop_front();

        printf("%d ", dq.front().second);
    }
}