백준 12789 도키도키 간식드리미

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

12789번: 도키도키 간식드리미

스택을 하나 이용해서 주어진 N개의 수들을 순서대로(오름차순) 만들 수 있는지를 판단하는 문제다.

줄서있는 사람의 차례인 경우 통과시키고

차례가 아닌 경우 스택에 집어넣는다.

스택에 쌓다보면, 현재 차례인 사람을 1)줄 서있는사람, 2)스택에 쌓인사람 두 경우 모두 비교해줘야한다.

둘 중 한명의 차례라면 그대로 내보내면 되고, 둘 다 아닌 경우엔 일단 스택에 넣어주는 수밖에 없다.

 

#include <iostream>
#define fio cin.tie(0)->sync_with_stdio(0)
using namespace std;

#include <queue>
#include <stack>
int main(){
    fio;
    int N; cin >> N;
    queue<int> standing;
    for(int i=0; i < N; i++){
        int tmp; cin >> tmp;
        standing.push(tmp);
    }
    stack<int> wait;
    int ack = 1;
    while(!standing.empty()){
        if(standing.front() == ack){//줄 선 사람이 차례면
            standing.pop();
            ack++;
        }else{//줄 선 사람 차례가 아니면, 옆 대기선을 본다
            if(!wait.empty()){//옆 대기선이 안비었으면확인해보자
                if(wait.top() == ack){
                    wait.pop();
                    ack++;
                }else{
                    wait.push(standing.front());
                    standing.pop();
                }
            }else{//옆 대기선 비어있다.
                wait.push(standing.front());
                standing.pop();
            }
        }
    }
    while(!wait.empty() && ack == wait.top()){
        wait.pop();
        ack++;
    }

    if(wait.empty())
        cout << "Nice";
    else
        cout << "Sad";
    return 0;
}