[백준 12789] 도키도키 간식드리미

🔗알고리즘 문제

자료구조 문제를 계속 연습하던 도중 만나게 된 반가운 스택문제였다. 평소에 스택 자료구조를 좋아하기도 하고 스택 문제에는 자신이 있어 쉽게 해결할 수 있었다. 역시 스택 문제는 생각하기 재밌는거 같다.

알고리즘 분석

문제가 길어 읽는데에 시간이 좀 걸렸지만 결국은 주어진 숫자들이 temp 스택을 사용하였을 때 올바른 순서로 출력될 수 있는지 없는지를 판단하는 문제이다.

* temp 스택?

주어진 숫자가 올바른 숫자가 아닐 시 잠시 보관할 수 있는 공간이다.
정답 출구로 나갈 수는 있지만 숫자열로 돌아갈 수는 없다.

발상

문제에서 표현한대로 한 사람씩 1열로만 설 수 있는 공간은 후입선출 구조를 나타내고 있어 Stack 자료구조를 활용하여야겠다고 생각하였다.

처음에는 문제를 그대로 코드로 옮겨 주어진 숫자가 올바르지 않을 시 temp 스택에 담고 올바르다면 출력하는 코드를 작성하였다.

if(num == order){
	++order;
}
else{
	if(temp.empty() == false && temp.top() == order){
		temp.pop();
		++order;
	}
	else{
		temp.push(num);
	}
}

하지만 이러한 방식으로 할 경우

5 4 3 2 1 6 7 8 9 10 이러한 숫자열이 주어질 때 스택에 있는 숫자는 잘 빠져나가지만 원본 숫자들이 스킵되어 올바르지 않은 정답이 출력되었다.

스택에 숫자도 빼고 원본 숫자들도 유지하기 위하여 스택에서 값을 하나만 빼는것이 아닌 반복문을 사용하기로 하였다.

알고리즘 설계

1. 숫자를 입력받고 해당 숫자가 order와 똑같은지 확인한다.
   ㄴ 만약 똑같다면 그대로 order를 증가시킨다.
2. 숫자가 같지 않다면 스택의 맨 위에 값이 order와 같지 않을 때 까지 스택의 값을 제거하여준다.
3. 모든 숫자가 지나간 후에 스택에 값이 남아있다면 2번 과정을 다시 실행한다.

코드

#include<iostream>
#include<stack>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    stack<int> temp;

    int cnt;
    int order = 1;

    cin >> cnt;

    for(int i = 0; i < cnt; i++){
        int num;
        cin >> num;
        
        if(num == order){
            ++order;
        }
        else{
            while(temp.empty() == false && temp.top() == order){
                temp.pop();
                ++order;
            }
            temp.push(num);
        }
    }

    while(temp.empty() == false){
        if(temp.top() == order){
            ++order;
            temp.pop();
        }
        else{
            cout << "Sad";
            return 0;
        }
    }

    cout << "Nice";
}