백준17178 - 줄서기

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

17178번: 줄서기

스택과 큐와 우선순위 큐를 이용하여 풀었다. 우선 5개씩 입력을 큐에 넣었고 입장 순서를 구하기 위하여 우선순위 큐에 넣었다. 

 

현재 순서를 구하기 위한 과정은 다음과 같다.

1. 현재 순서를 대기열에서 발견한 경우는 스택에서 마지막 원소를 뽑는다.

2. 현재 순서를 줄에서 발견한 경우는 큐에서 첫번째 원소를 뽑는다.

3. 현재 순서를 대기열과 줄에서 발견하지 못한 경우는 스택에 대기열 첫번째 원소를 넣는다.

 

현재 줄에 서있는 사람이 없으면 다음 줄로 넘어간다.

 

안되는 조건으로는 현재 순서를 구하지 못하는 경우인데 대기열에 넣을 사람이 없는 경우다.

 

#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;

struct cmp {
    bool operator()(string a, string b) {
        if (a[0] > b[0]) {
            return true;
        }
        else if (a[0] == b[0]) {
            int num1 = stoi(a.substr(2, a.size()));
            int num2 = stoi(b.substr(2, b.size()));
            if (num1 > num2) {
                return true;
            }
            else {
                return false;
            }
        }
        else {
            return false;
        }
    } 
};


int main() {
    int n;
    int cnt = 1;
    stack<string> stk;
    queue<string> line[101];
    priority_queue<string, vector<string>, cmp> order;
    string s;

    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 5; j++) {
            cin >> s;
            line[i].push(s);
            order.push(s);
        }
    }

    while (!order.empty()) {
        if (!line[cnt].empty() && line[cnt].front() == order.top()) {
            line[cnt].pop();
            order.pop();
        }
        else if (!stk.empty() && stk.top() == order.top()) {
            stk.pop();
            order.pop();
        }
        else {
            if (!line[cnt].empty()) {
                stk.push(line[cnt].front());
                line[cnt].pop();
            }
            else {
                cout << "BAD";
                return 0;
            }
        }
        if (line[cnt].empty() && cnt != n) {
            cnt++;
        }
    }

    cout << "GOOD";
}