팀 큐 시뮬레이션 구현하기

팀 큐는 각 원소가 특정 팀에 속하는 자료구조입니다. 새로운 원소가 큐에 들어올 때, 큐의 앞에서부터 검사하여 같은 팀의 원소가 이미 존재하는지 확인합니다. 같은 팀원이 있다면 그 뒤에 바로 삽입되고, 없다면 큐의 가장 뒤에 추가됩니다. 디큐(dequeue) 작업은 일반 큐와 동일하게 앞에서부터 순서대로 처리됩니다. 이 문제는 이러한 팀 큐를 효율적으로 시뮬레이션하는 프로그램을 작성하는 것입니다.

입력

여러 개의 테스트 케이스가 주어집니다.
각 테스트 케이스는 팀의 수 t로 시작합니다.
이후 t개의 팀 설명이 주어지며, 각 설명은 팀에 속한 원소의 개수와 원소 목록으로 구성됩니다. 원소는 0에서 999999 사이의 정수이며, 한 팀은 최대 1000개의 원소를 가질 수 있습니다.
그 다음으로 명령어 목록이 주어집니다. 명령어 종류는 세 가지입니다:
- ENQUEUE x: 원소 x를 팀 큐에 추가
- DEQUEUE: 큐의 첫 번째 원소를 처리하고 제거
- STOP: 테스트 케이스 종료
입력의 끝은 t=0으로 표시됩니다.

주의: 테스트 케이스 하나에 최대 20만 개의 명령어가 있을 수 있으므로, 인큐와 디큐 모두 상수 시간에 처리되어야 합니다.

출력 각 테스트 케이스마다 "Scenario #k"를 출력한 후, 각 DEQUEUE 명령어에 대해 디큐된 원소를 한 줄에 하나씩 출력합니다. 각 테스트 케이스 후에는 빈 줄을 출력합니다.

예제 입출력:

2
3 101 102 103
3 201 202 203
ENQUEUE 101
ENQUEUE 201
ENQUEUE 102
ENQUEUE 202
ENQUEUE 103
ENQUEUE 203
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
DEQUEUE
STOP
0

Scenario #1
101
102
103
201
202
203

효율적인 구현을 위해서는 각 원소의 팀 번호를 매핑하는 자료구조와 팀별 큐, 그리고 팀 자체의 순서를 관리하는 큐가 필요합니다. 다음은 C++로 작성된 예시 코드입니다.

#include <iostream>
#include <unordered_map>
#include <queue>
#include <string>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int teamCount, testCase = 0;
    while (cin >> teamCount && teamCount != 0) {
        testCase++;
        cout << "Scenario #" << testCase << '\n';
        
        unordered_map<int, int> elemToTeam;
        for (int i = 0; i < teamCount; ++i) {
            int count, elem;
            cin >> count;
            while (count--) {
                cin >> elem;
                elemToTeam[elem] = i;
            }
        }
        
        queue<int> teamOrder;
        vector<queue<int>> teamQueues(teamCount);
        string command;
        
        while (cin >> command) {
            if (command[0] == 'S') break;
            
            if (command[0] == 'E') {
                int x;
                cin >> x;
                int teamId = elemToTeam[x];
                if (teamQueues[teamId].empty()) {
                    teamOrder.push(teamId);
                }
                teamQueues[teamId].push(x);
            } else if (command[0] == 'D') {
                int frontTeam = teamOrder.front();
                int result = teamQueues[frontTeam].front();
                cout << result << '\n';
                teamQueues[frontTeam].pop();
                if (teamQueues[frontTeam].empty()) {
                    teamOrder.pop();
                }
            }
        }
        cout << '\n';
    }
    return 0;
}

위 코드에서는 unordered_map을 사용하여 각 원소의 팀 번호를 빠르게 찾고, queue를 사용하여 팀 순서를 관리합니다. 각 팀의 큐가 비어있을 때만 teamOrder에 팀 번호를 추가하고, 디큐 시 해당 팀의 큐가 비면 teamOrder에서 제거합니다. 이렇게 하면 모든 연산이 O(1)에 처리됩니다.

태그: UVa Team Queue 자료구조 큐 시뮬레이션

7월 28일 00:38에 게시됨

괴물 클럽

팀 큐 시뮬레이션 구현하기

인기 태그