[BOJ알고리즘, C++]#12789_도키도키 간식 드리미, 스택, 큐

 

[BOJ알고리즘, C++]#12789_도키도키 간식 드리미

 

BOJ 알고리즘 문제 풀이, 12789번 문제 도키 도키 간식 드리미

스택과 큐를 활용하여 푸는 문제

 

---

 

Overview

 

1. 문제
2. 풀이
3. 코드

 

#1. 문제

 

 

#2. 풀이

1. 스택

[자료 구조]#0_선형 자료구조

 

[Basic C++] #64_stack

 

Details

 

• 스택은 LIFO 방식으로 동작하는 같은 구조와 같은 크기의 데이터를 오직 한 방향으로만 삽입/제거 가능한 선형 자료구조입니다.

 

2. 큐

[자료 구조]#0_선형 자료구조

 

[Basic C++] #67_queue

 

Details

 

• 큐는 FIFO(선입 선출) 방식으로 동작하는 데이터 목록의 한쪽 끝에서는 데이터의 삽입만 이루어지며, 다른 한쪽 끝에서는 데이터의 삭제만 이루어지는 선형 자료구조입니다.

 

3. 스택과 큐 활용

1. 먼저, 맨 앞 사람만 이동 가능한 줄은 "큐" 자료구조를 통해 구현합니다.
2. 그리고, 다른 한 줄은 "스택" 자료구조를 활용합니다.
3. 입력 값을 큐에 차례대로 삽입합니다.
4. 큐의 front, 즉 맨 앞에 있는 숫자가 현재 차례가 맞다면 pop을 수행하고 다음 차례로 넘어갑니다.
5. 큐의 front, 즉 맨 앞에 있는 숫자가 현재 차례가 아니라면, stack의 top을 살펴보고 현재 차례가 맞다면, 똑같이 pop을 수행하고 다음 차례로 넘어갑니다.
6. 스택의 top, 즉 맨 앞에 있는 숫자가 현재 차례가 맞다면 pop을 수행하고 다음 차례로 넘어갑니다.
7. 스택의 top, 즉 맨 앞에 있는 숫자가 현재 차례가 아니라면, "Sad"를 출력하고 함수를 종료합니다. 
8. 큐와 스택을 순회하고 위 작업들을 모두 성공적으로 마치면, "Nice"를 출력합니다.

 

#3. 코드

 

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

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    
    int N;
    queue<int> q;
    stack<int> s;
    cin >> N;
    
    while(N--)
    {
        int num;
        cin >> num;
        
        q.push(num);
    }
    
    int order = 1;
    while(!q.empty())
    {
        int cur = q.front();
        if(cur == order)
        {
            q.pop();
            order++;
        }
        else
        {
            if(!s.empty() && order == s.top())
            {
                order++;
                s.pop();
            }
            else
            {
                s.push(cur);
                q.pop();
            }
        }
    }
    while(!s.empty())
    {
        if(order == s.top())
        {
            order++;
            s.pop();
        }
        else
        {
            cout << "Sad";
            return 0;
        }
    }
    
    cout << "Nice";
    
    return 0;
}