[백준 C++] 12789번 : 도키도키 간식드리미

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

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

풀이 :
- 정렬되어 있지 않은 수열을 스택의 방식을 이용해 정렬할 수 있는지 여부를 물어보는 문제
- 스택의 방식이란, last in first out으로, 제일 뒤에 들어간 요소가 제일 먼저 나오는 것
1 주어진 배열을 탐색하며 제일 작은 값이 나오기 전까지 스택에 넣어준다
2 제일 작은 값을 만나면 값을 빼준다
3 현재 인덱스에 있는 값이 직전에 빠진 값보다 1 클 경우, 현재 인덱스의 값도 빼준다
4 현재 인덱스에 있는 값이 직전에 빠진 값보다 2 이상 클 경우, 스택을 탐색하며 정렬되지 않는 값이 나올 때가지 스택에서 값을 뺀다
5 그리고 스택에 현재 인덱스의 값을 넣는다
6 배열의 탐색이 끝난 후 스택에 쌓인 값이 있다면, 스택을 탐색한다
7 쌓인 스택의 값을 하나씩 꺼냈을 때 정렬되지 않는다면 바로 break해준다 -> 정렬되지 않는 여부가 결정되는 유일한 부분
 
- 예제를 통해 스택의 변화를 살펴보자

5
5 4 1 3 2

for문{
1을 만나기 전까지 스택에 값을 넣는다
스택 : 5 4

1을 만나서 저장한다
스택 : 5 4
num : 1

3을 만났는데 저장된 1보다 2크고, 스택 제일 위에 있는 값도 4라서 3을 스택에 쌓는다
스택 : 5 4 3
num : 1

2를 만났고, 2는 1보다 1크기 때문에 num에 2를 넣어준다
스택 : 5 4 3
num : 2
for문 종료}

스택이 비어있지 않기 때문에 while문에 들어간다
while문{
스택 : 5 4 3
num : 2

스택의 제일 위에 있는 값 3은 num의 값 2보다 1크기 때문에 num에 3을 넣고,
스택에서 3을 빼준다
스택 : 5 4
num : 3

스택의 제일 위에 있는 값 4는 num의 값 3보다 1크기 때문에 num에 4를 넣고,
스택에서 4를 빼준다
스택 : 5
num : 4

스택의 제일 위에 있는 값 5는 num의 값 4보다 1크기 때문에 num에 5를 넣고,
스택에서 4를 빼준다
스택 : 
num : 5
while문 종료}

만약 배열이 3 5 4 1 2로 되어있다면,
for문이 종료되었을 때 num에는 2, 스택에는 3 5 4가 들어있고, 4는 2보다 2 크기 때문에 정렬이 불가능해진다
 
코드 :

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

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

    int n, num = 0, arr[10005];
    bool res = true; //정렬 여부를 나타낼 res변수
    stack<int> line;

    cin >> n;
    for(int i=0; i<n; i++){
        cin >> arr[i];
    }
    for(int i=0; i<n; i++){
        if(arr[i] == num+1){ //현재 인덱스의 값과 num+1의 값이 같다면
            num = arr[i]; //num의 값 변경
        }else{
            while(!line.empty()){ //스택에 쌓인 값이 있다면 들어가는 while문
                if(line.top() == num+1){ //스택 제일 위에 있는 값이 num+1의 값과 같다면
                    num = line.top(); //num의 값 변경
                    line.pop(); //스택에서 값 삭제
                }else{ //while문의 조건이 스택이 비어있지 않을 때이기 때문에, 무한 반복을 할 수 있다
                    break; //따라서 if문의 조건에 맞지 않으면 break로 탈출해줘야 한다
                }
            }
            line.push(arr[i]); //현재 인덱스의 값을 스택에 넣어준다
        }
    } //스택이 비어있다면 밑의 while문에 들어가지 않고, res의 값 또한 변경되지 않아 Nice가 출력된다 
    while(!line.empty()){ //스택이 비어있지 않다면, 위의 while문과 같은 동작을 한다
        if(line.top() == num+1){
            num = line.top();
            line.pop();
        }else{
            res = false; //다만 이 while문의 경우 조건에 맞지 않으면 더이상 정렬할 수 있는 방법이 없기 때문에
            break; //res의 값을 변경하고 탈출한다
        }
    }
    (res ? cout << "Nice\n" : cout << "Sad\n");
}