문제 푼 날짜 : 2021-11-01

문제

문제 링크 : https://www.acmicpc.net/problem/12789

접근 및 풀이

스택과 큐를 이용하여 풀 수 있는 문제였다.
아래의 생각대로 코드를 구현하였다.

1. 주어진 입력들을 큐에 넣어주고, 번호표 1번부터 체크해준다.
2. 큐의 front에 번호표와 같은 값이면 pop해준다.(번호표 +1)
   2-1. 다른 값이면 스택의 top값을 봐준다.
   2-2. 스택의 top에 번호표와 같은 값이 있으면, 그 값을 pop해준다. (번호표 +1)
   2-3. 번호표와 같은 값이 없다면, 큐의 front 값을 push해준다.
3. 큐가 빌때까지 2번의 과정을 반복한ㄷ.ㅏ
4. 남은 스택을 pop하면서 번호표 순서대로 pop이 되지 않으면 "Sad" 출력.
5. 정상적이면 "Nice" 출력.

코드

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int N;
    cin >> N;
    
    queue<int> q;
    stack<int> st;
    int next = 1;
    for (int i = 0, num; i < N; i++) {
        cin >> num;
        q.push(num);
    }
    
    while (!q.empty()) {
        if (q.front() == next) {
            q.pop();
            next++;
        } else {
            if (!st.empty() && st.top() == next) {
                st.pop();
                next++;
            } else {
                st.push(q.front());
                q.pop();
            }
        }
    }
    
    while (!st.empty()) {
        if (st.top() != next) {
            cout << "Sad";
            return 0;
        }
        st.pop();
        next++;
    }
    cout << "Nice";
    return 0;
}

결과

피드백

스택과 큐는 언제든지 떠올릴 수 있어야하는 다재다능한 자료구조들인 것 같다.