백준 12789번 [도키도키 간식드리미](C++) -yes6686- 티스토리

백준 문제 풀이: 12789 [도키도키 간식드리미]

---

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

문제 설명:

아이들이 1번부터 n번까지 번호가 붙어 줄을 서 있습니다. 이 아이들에게 순서대로 간식을 나눠주려 합니다. 하지만 아이들은 자기 순서가 아닐 때도 간식을 받으려 하고, 이를 해결하기 위해 보조 스택을 사용합니다.

아이들에게 간식을 순서대로 줄 수 있다면 "Nice", 그렇지 않다면 "Sad"를 출력하는 문제입니다.

---

문제 해결 코드

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

queue q; // 줄을 서 있는 아이들의 순서
stack s; // 보조 스택

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n; // 아이들의 수
    cin >> n;

    // 줄 서 있는 아이들 입력
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        q.push(x);
    }

    int i = 1; // 간식을 받을 현재 순서
    while (!q.empty()) {
        int x = q.front();
        if (x == i) { 
            // 간식을 받을 차례인 경우
            i++;
            q.pop();
        } else {
            // 보조 스택 처리
            if (!s.empty() && s.top() == i) {
                i++;
                s.pop();
            } else {
                s.push(x);
                q.pop();
            }
        }
    }

    // 보조 스택에 남은 아이들을 처리
    while (!s.empty()) {
        int x = s.top();
        s.pop();
        if (x != i) {
            cout << "Sad\n";
            return 0;
        }
        i++;
    }

    cout << "Nice\n"; // 모든 아이들에게 간식을 줄 수 있는 경우
    return 0;
}

예제 입력:

5
5 4 1 3 2

예제 출력:

Nice

---

코드 설명

• 핵심 알고리즘: 큐와 스택을 사용하여 현재 순서에 맞는 간식을 줄 수 있는지 시뮬레이션합니다.
• 구현 세부사항:
  • 큐는 아이들이 줄 서 있는 순서를 나타내며, 보조 스택은 간식을 받을 순서를 기다리는 아이들을 저장합니다.
  • 보조 스택의 맨 위와 현재 순서가 일치하면 간식을 나눠줍니다.
  • 큐와 스택이 모두 비었을 때 정상적으로 간식을 줄 수 있으면 "Nice"를 출력합니다. 그렇지 않으면 "Sad"를 출력합니다.
• 시간 복잡도:
  • 큐와 스택 연산은 모두 O(1)이며, 입력 크기 n에 대해 한 번씩 접근하므로 O(n)입니다.

---

결과

아이들이 간식을 받을 순서를 정확히 처리하여 결과를 출력합니다. 이 문제는 큐와 스택의 동작 원리를 이해하고 활용하는 데 적합합니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!