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

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

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

어려웠던 문제/./

---

문제

인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두근 설레서 시험 공부에 집중을 못 한다. 이번 중간고사에서도 역시 승환이는 설레는 가슴을 안고 간식을 받기 위해 미리 공지된 장소에 시간 맞춰 도착했다. 그런데 이게 무슨 날벼락인가! 그 곳에는 이미 모든 학생들이 모여있었고, 승환이는 마지막 번호표를 받게 되었다. 설상가상으로 몇몇 양심에 털이 난 학생들이 새치기를 거듭한 끝에 대기열의 순서마저 엉망이 되고 말았다. 간식을 나눠주고 있던 인규는 학우들의 터져 나오는 불만에 번호표 순서로만 간식을 줄 수 있다고 말했다. 

그제야 학생들이 순서대로 줄을 서려고 했지만 공간이 너무 협소해서 마음대로 이동할 수 없었다. 다행히도 대기열의 왼쪽에는 1열로 설 수 있는 공간이 존재하여 이 공간을 잘 이용하면 모두가 순서대로 간식을 받을 수 있을지도 모른다. 자칫 간식을 못 받게 될지도 모른다는 위기감을 느낀 승환이는 자신의 컴퓨터 알고리즘적 지식을 활용해 과연 모든 사람들이 순서대로 간식을 받을 수 있는지 확인하는 프로그램을 만들기로 했다. 만약 불가능 하다면 승환이는 이번 중간고사를 망치게 될 것 이고 가능하다면 힘을 얻어 중간고사를 잘 볼 수 있을지도 모른다.

사람들은 현재 1열로 줄을 서있고, 맨 앞의 사람만 이동이 가능하다. 인규는 번호표 순서대로만 통과할 수 있는 라인을 만들어 두었다. 이 라인과 대기열의 맨 앞 사람 사이에는 한 사람씩 1열이 들어갈 수 있는 공간이 있다. 현재 대기열의 사람들은 이 공간으로 올 수 있지만 반대는 불가능하다. 승환이를 도와 프로그램을 완성하라.

현재 간식 배부 공간을 그림으로 나타내면 다음과 같다.

위 예제는 다음 그림과 같이 움직였을 때 모두가 순서대로 간식을 받을 수 있다..

---

입력

입력의 첫째 줄에는 현재 승환이의 앞에 서 있는 학생들의 수 N(1 ≤ N ≤ 1,000,자연수)이 주어진다.

다음 줄에는 승환이 앞에 서있는 모든 학생들의 번호표(1,2,...,N) 순서가 앞에서부터 뒤 순서로 주어진다.

---

출력

승환이가 무사히 간식을 받을 수 있으면 "Nice"(따옴표는 제외)를 출력하고 그렇지 않다면 "Sad"(따옴표는 제외)를 출력한다.

---

일단 벡터,큐,스택을 만들어두고, 입력을 N번 받고 큐와 배열에 모두 넣어둔다. 예제가 5,4,1,3,2일떄, 5개 모두 큐에 넣어준다.

번호를 1로 넣고, 큐의 제일 앞에 있는 값(q.front())와 비교를 한다.

 

-번호가 큐의 제일 앞에 있는 값과 같은 경우 : 벡터에 큐의 상단 값을 넣어주고, 번호를 1 증가시킨다. 또한 큐의 Pop연산을 한다.

-번호가 큐의 제일 앞에 있는 값과 다른 경우:

 

이떄, 2가지 경우로 나뉜다.

1)스택이 비어있는 경우 : 스택이 비어있다면 그냥 스택에 큐의 제일 앞에있는 값을 넣고, 큐의 Pop연산을 한다.

 

2)스택이 비어있지 않은 경우 : 이때, 스택의 상단 값과 번호를 비교한다.

 

2)-1: 스택의 상단 값(Top)과 번호가 같은 경우

->벡터에 스택의 상단 값을 넣고, 스택의 Pop연산을 하고, 번호를 1 증가시킨다.

 

2)-2: 스택의 상단 값(Top)과 번호가 다른 경우

->스택에 큐의 상단 값을 넣어주고 , 큐를 Pop한다.

 

이 과정을 Q의 원소가 없을때까지 반복한다.

 

그 후 스택이 비어있을 때까지, 벡터에 스택의 Top값을 넣어주고 스택을 Pop한다.

 

 

배열을 정렬하고, 벡터의 값과 비교를 하는데, 이 값이 서로 다르다면 Sad출력을 하고

return 0으로 프로그램 종료를 한다.

 

만약 프로그램이 종료 안된 상태라면 Nice를 출력한다.

---

전체 소스 코드->

#include <iostream>

#include <vector>

#include <algorithm>

#include <queue>

#include <stack>

using namespace std;

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

 

int main(void){

    queue<int> q;

    vector<int> v;

    stack<int> st;

 

    int arr[1001];

    int n;

    cin >> n;

 

    for(int i = 0;i<n;i++){

        cin >> arr[i]; //배열과 큐에 모두 넣어준다.

        q.push(arr[i]);

    }

 

    int num = 1; //번호

    while(!q.empty()){ //큐가 빌때까지 반복한다.

        if(q.front() == num){ //큐의 상단(front)값과 번호가 같은 경우

            v.push_back(num); //벡터에 넣어주고, 큐를 Pop하고, 번호를 증가시킨다

            q.pop();

            num++;

        }

        else if(q.front() != num){ //큐의 상단(front)값과 번호가 다른 경우 2가지로 나뉜다

           

            if(st.empty()){ //스택이 비어 있는 경우

                st.push(q.front());//스택에 큐의 상단 값을 넣고, 큐를 Pop해준다

                q.pop();

            }

            else if(!st.empty()){ //스택이 비어있지 않은 경우

                if(st.top() == num){

         //스택의 Top값과 번호가 같다면 벡터에 스택의 Top을 넣고, 스택을 Pop해주고,번호를 증가시킨다

                    v.push_back(st.top());

                    st.pop();

                    num++;      

                }

         //스택의 Top값과 번호가 다르다면 스택에 큐의 상단 값을 넣고, 큐를 Pop해준다      

                else if(st.top() != num){

                    st.push(q.front());

                    q.pop();

                }

            }

        }

    }

 

   

    while(!st.empty()){  //스택이 비어있을 때까지

        v.push_back(st.top()); //벡터에 스택의 Top값 넣고, 스택 Pop해주기

        st.pop();

    }

    sort(arr,arr+n); //배열의 값을 오름차순 정렬해주고 벡터와 비교를 시작

    for(int i = 0;i<n;i++){ //벡터의 i번째 값과 i+1이 다르다면 Sad출력 후 , 프로그램 종료

        if(v[i] != i+1){

            cout << "Sad";

            return 0;

        }

    }

    cout << "Nice"; //프로그램이 종료되지 않았다면 Nice출력

    return 0;

 

}