(C++) - 백준(BOJ) 17178번 : 줄서기

www.acmicpc.net/problem/17178

17178번: 줄서기

stack으로 구현한 문제였습니다.

 

풀이방법

 1. 입장 순서 정렬

 먼저 입장해야하는 순서를 티켓정보를 정렬함으로써 알아낼 수 있습니다. 정렬시 주의해야할 점은 티켓의 정보 중 앞 알파벳이 같은 티켓이라면 -다음 숫자가 적은 것이 앞으로 와야합니다. 함수로 정렬 기준을 마련하지 않고 그냥 sort하게 된다면 A-102가 A-4보다 뒤로가게 됩니다. string으로는 A-102가 A-4보다 큰 값이기 때문입니다. 따라서 substr함수를 이용해 102, 4라는 정보를 int형으로 변환한 뒤 더 작은 값이 앞에 오도록 정렬기준을 세워야 합니다.

 

 2. stack push, pop

  정렬 후에는 기존 줄 서 있는 사람들의 티켓 정보와 정렬된 순서배열을 가장 왼쪽부터 살펴보면서 stack에 push할지 pop할지 결정합니다.

  2-1. 줄의 가장 왼쪽 사람과 현재 순서가 맞다면 해당 사람은 바로 입장이 가능합니다. 

  2-2. 대기열 stack이 차있고 top == 현재 순서라면 대기열에 있던 top()에 위치한 인원은 입장 가능합니다. pop()

  2-3. else의 경우엔 무작정 대기열 stack에 넣어줍니다. 

 

 3. bad good여부 판별

  stack이 차 있는 동안 stack에 남아있는 사람들은 이제 순서대로 pop하면서 제대로된 순서인지 확인합니다. 만약 top의 순서와 현재 순서가 다르다면 bad이므로 flag를 true로 만들어준 후 loop를 탈출합니다.

 

 4. 출력

 

Code

#include <bits/stdc++.h>
using namespace std;
int n,i,j, flag;
vector <string> ticketInfo;
vector <string> sequence;
stack <string> s;

bool cmp(string &a, string &b){
    string alpha = a.substr(0,1);
    string alpha2 = b.substr(0,1);
    int num1 = stoi(a.substr(2));
    int num2 = stoi(b.substr(2));
    if(alpha == alpha2) return num1 < num2;
    return a < b;
}

int main(){
    cin >> n;
    for(int i = 0; i < n*5; i++){
        string ticket;
        cin >> ticket;
        ticketInfo.push_back(ticket);
    }
    sequence = ticketInfo;
    sort(sequence.begin(),sequence.end(),cmp);
    
    while(i < 5 * n && j < 5 * n){
        if(ticketInfo[i] == sequence[j]) i++, j++;
        else if(!s.empty() && s.top() == sequence[j]) s.pop(), j++;
        else s.push(ticketInfo[i++]);
    }

    while(!s.empty()){
        if(s.top()!=sequence[j++]){
            flag = 1;
            break;
        }
        s.pop();
    }   

    if(flag) cout << "BAD\n";
    else cout << "GOOD\n";
}