백준 12789 도키도키 간식드리미 / C++

문제 : 12789

풀이 point

스택을 활용하여 사람들을 대기열에서 빼내고 자신의 순서일때 다시 집어넣을 수 있다.

풀이 방법

스택을 활용한다. 만약 자신의 차례가 아닌 사람은 스택에 집어넣는다. 또 스택의 top이 자신의 차례면 스택에서 제거한다.

코드

//백준 12789, 도키도키 간식드리미
#include <iostream>
#include <stack>

int people[1'000];
int N;
std::stack<int> s;

int main(){

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
    
    std::cin >> N;

    for(int i{0}; i<N; ++i){
        std::cin >> people[i];
    }

    int turn{1}; int i{0};
    while(i<N){
        if(people[i] != turn){
            if(s.empty() || s.top() != turn){
                s.push(people[i]);
                ++i;
            }
            else{
                s.pop(); 
                ++turn;
            }
        }
        else{
            ++turn;
            ++i;
        }
    }

    if(s.size() <= 1){
        std::cout << "Nice";
        return 0;
    }
    
    int prev = s.top();
    s.pop();

    while(!s.empty()){
        int curr = s.top();
        s.pop();
        if(curr < prev){
            std::cout << "Sad";
            return 0;
        }
    }

    std::cout << "Nice";

    return 0;
}