C++로 시퀀스 쿼리 처리하기: 삽입, 출력, 정렬 구현 방법

문제 소개

빈 시퀀스가 하나 주어져 있고, 이 시퀀스에 대해 처리해야 할 n개의 쿼리가 있다고 가정해 봅시다. 쿼리는 배열 queries에 저장되어 전달되며, 각 쿼리는 {query, data} 형식을 따릅니다. 쿼리의 종류는 다음 세 가지입니다.

query = 1 : 전달된 데이터(data)를 시퀀스의 맨 뒤에 추가합니다.
query = 2 : 시퀀스 맨 앞의 원소를 출력하고, 해당 원소를 시퀀스에서 제거합니다.
query = 3 : 시퀀스 전체를 오름차순으로 정렬합니다.

단, 쿼리 타입 2와 3에서는 항상 data = 0이 주어집니다.

예제 살펴보기

n = 9이고, queries = {{1, 5}, {1, 4}, {1, 3}, {1, 2}, {1, 1}, {2, 0}, {3, 0}, {2, 0}, {3, 0}}인 경우를 생각해 보겠습니다. 이때 출력 결과는 5와 1입니다.

각 쿼리가 실행된 직후의 시퀀스 상태는 아래와 같습니다.

쿼리 1 : {5}
쿼리 2 : {5, 4}
쿼리 3 : {5, 4, 3}
쿼리 4 : {5, 4, 3, 2}
쿼리 5 : {5, 4, 3, 2, 1}
쿼리 6 : {4, 3, 2, 1} — 맨 앞의 5를 출력
쿼리 7 : {1, 2, 3, 4} (오름차순 정렬)
쿼리 8 : {2, 3, 4} — 맨 앞의 1을 출력
쿼리 9 : {2, 3, 4}

풀이 접근 방법

이 문제는 일반 큐(queue)와 우선순위 큐(priority_queue)를 함께 사용하면 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

정렬되기 전의 원소들은 일반 큐 q에 순서대로 보관합니다.
정렬 쿼리(타입 3)가 들어오면, 큐에 남아 있는 모든 원소를 꺼내 우선순위 큐 priq로 옮깁니다.
C++의 priority_queue는 기본적으로 최대 힙으로 동작하므로, 값을 음수로 변환하여 저장하면 최소 힙처럼 활용할 수 있습니다. 즉, 음수 값 중 가장 큰 값(= 원래 값 중 가장 작은 값)이 항상 top에 위치하게 됩니다.
출력 쿼리(타입 2)가 들어오면, 우선순위 큐가 비어 있는 경우에는 일반 큐의 맨 앞 원소를 출력하고, 그렇지 않으면 우선순위 큐의 top 원소에 음수 부호를 붙여 출력합니다.

위 접근 방식의 의사 코드는 다음과 같습니다.

priority_queue<int> priq
class queue q 선언
for i := 0부터 i < n까지 반복 (i는 1씩 증가):
    operation := queries[i]의 첫 번째 값
    만약 operation이 1이라면:
        x := queries[i]의 두 번째 값
        x를 q에 삽입
    그렇지 않고 operation이 2라면:
        priq가 비어 있다면:
            q의 첫 번째 원소 출력
            q에서 첫 번째 원소 삭제
        그렇지 않다면:
            -(priq의 top 원소) 출력
            priq에서 top 원소 삭제
    그렇지 않고 operation이 3이라면:
        q가 빌 때까지 반복:
            -(q의 첫 번째 원소)를 priq에 삽입
            q에서 원소 삭제

C++ 구현 예제

아래 구현 예제를 통해 실제 동작을 더 자세히 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;

void solve(int n, vector<pair<int, int>> queries){
   priority_queue<int> priq;
   queue<int> q;
   for(int i = 0; i < n; i++) {
      int operation = queries[i].first;
      if(operation == 1) {
         int x;
         x = queries[i].second;
         q.push(x);
      } else if(operation == 2) {
         if(priq.empty()) {
            cout << q.front() << endl;
            q.pop();
         } else {
            cout << -priq.top() << endl;
            priq.pop();
         }
      } else if(operation == 3) {
         while(!q.empty()) {
            priq.push(-q.front());
            q.pop();
         }
      }
   }
}

int main() {
   int n = 9;
   vector<pair<int, int>> queries = {{1, 5}, {1, 4}, {1, 3}, {1, 2}, {1, 1}, {2, 0}, {3, 0}, {2, 0}, {3, 0}};
   solve(n, queries);
   return 0;
}

입력

9, {{1, 5}, {1, 4}, {1, 3}, {1, 2}, {1, 1}, {2, 0}, {3, 0}, {2, 0}, {3, 0}}

출력

5
1

마무리

이 풀이에서 삽입 연산은 O(1), 출력 연산은 O(log n)의 시간 복잡도를 가지며, 정렬 연산은 큐에 남아 있는 원소들을 힙으로 옮기는 비용만큼 소요됩니다. 결과적으로 전체 알고리즘은 대략 O(n log n) 안에 동작하므로, 정렬 쿼리마다 매번 정렬 함수를 호출하는 단순한 구현보다 훨씬 효율적입니다. 이처럼 큐와 우선순위 큐의 특성을 적절히 조합하면 "삽입–출력–정렬"이 섞여 있는 쿼리 문제도 손쉽게 처리할 수 있습니다.