[백준 22234번] 가희와 은행 (C++)

https://www.acmicpc.net/problem/22234

 

큐를 사용하여 시뮬레이션 하는 문제가 이전에 코딩테스트에 출제되어서 이번에 도장깨기를 하고자 풀어보았다.

 

큐 문제를 풀 때는 가장 중요한 것이 보통 시뮬레이션이 동반되기 때문에 문제를 정확히 파악하는 것이 중요하다.

그리고 그림으로 그려가면서 어떤 지점에서 큐를 사용할지 가상으로 시뮬레이션해보는 것이 매우 중요한 것 같다.

 

이 문제를 시뮬레이션 해보면

 

 

위 시뮬레이션을 보자. 1, 2에서 새로운 아이디가 들어왔는데 1이 아직 안 끝났으므로 맨 뒤로 들어간 모습이다. 이것을 의사코드로 생각해보면

 

if 현재 고객의 상담이 끝나면: 이후 온 사람들이 있는지 검사하고 이전에 온 사람들이 있으면 큐에 삽입

 

그렇다면 이제 온 사람들을 관리할 큐가 하나 더 필요하다는 것을 알 수 있다. 그리고 이것을 우선순위큐로 관리한다. 

 

if 현재 고객의 상담이 끝나면: 
	while : 이후 온 사람들을 모아놓은 우선순위 큐
    	if 가장 먼저 온 사람들 부터 검사하며 현재 시간보다 일찍 왔거나 같으면 큐에 삽입
        else 나가기

 

이렇게 의사코드가 업데이트 되고 이제 코드를 만들어보자

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

struct customer{
    int id;
    int needTime;
    int visitedTime;
};

bool comp(customer &c1, customer &c2){
    return c1.visitedTime < c2.visitedTime;
}

int main(){
    int N, T, W; cin >> N >> T >> W;

    queue<pair<int, int>> q; // 아이디, 필요시간
    priority_queue<pair<int, pair<int, int>>> pq;

    for(int i = 0; i < N; i++){
        int id, need;
        cin >> id >> need;

        q.push({id, need});
    }

    int M; cin >> M;
    int minusOneTime = -1;

    for (int i = 0; i < M; i++){
        int id, need, visited; cin >> id >> need >> visited;

        pq.push({-visited,{id,need}});
    }

    int nowTime = 1;
    vector<pair<pair<int, int>, int>> answer;
    while(!q.empty()){
        int id = q.front().first;
        int needTime = q.front().second;
        q.pop();

        int preTime = nowTime;
        
        if(needTime <= T){ // 업무 완료 가능
            answer.push_back({{nowTime, nowTime + needTime - 1}, id});
            nowTime += needTime;

            while(!pq.empty()){
                int visited = -pq.top().first;
                int need = pq.top().second.second;
                int id = pq.top().second.first;
                //cout << nowTime << ' ' << visited << endl;
                if(visited <= nowTime - 1){ // 들어와야함
                    q.push({id, need});
                    pq.pop();
                }else{
                    break;
                }
            }
        }else{
            answer.push_back({{nowTime,nowTime + T - 1}, id});
            needTime -= T;
            nowTime += T;   

            while(!pq.empty()){
                int visited = -pq.top().first;
                int need = pq.top().second.second;
                int id = pq.top().second.first;
                //cout << nowTime << ' ' << visited << endl;

                if(visited <= nowTime - 1){ // 들어와야함
                    q.push({id, need});
                    pq.pop();
                }else{
                    break;
                }
            }

            q.push({id, needTime});
        }

        if(preTime <= W && nowTime >= W){
            minusOneTime = id;
        }
    }

    for(int i = 0; i < answer.size(); i++){
        int start =  answer[i].first.first;
        int end =  answer[i].first.second;
        int id = answer[i].second;

        //cout << start << ' ' << end << ' ' << id << endl;

        for(; start <= end; start++){
            cout << id << '\n';

            if(start == W - 1) {
                cout << minusOneTime << '\n';

                return 0;
            }
        }
    }
}