[스택] 백준 1874번 스택수열)

백준 1874번

스택 수열

처음에 문제가 무슨 말을 하는지 몰라서 좀 헤맸지만 직접 예제를 그려보니 의외로 금방 이해가 됐다.

문제에서 주어진 예시처럼 1~8까지의 수가 주어지면,

push(1) push(2) push(3) push(4) pop(4) pop(3) push(5) push(6) pop(6) push(7) push(8) pop(8) pop(7) pop(5) pop(2) pop(1)

pop 한 숫자들만 다시 모아서 수열을 만든다고 생각하면 된다.

필요 재료

---

우선 오름차순으로 push 하기 때문에 어디까지 push 했었는지 기억하는 변수가 필요하다. (ex- cur_pos)

이 변수는 push 하는 경우 증가한다.

그리고 입력으로 주어지는 수열을 담을 벡터도 필요하다. (ex- target)

목표로 하는 수열을 어디까지 만들었는지 표시할 변수도 필요하다. (ex-target_pos)

이 변수는 pop 하는 경우 증가한다.

push pop을 시뮬레이션 할 스택도 하나 필요하다. (ex-generator)

완료/실패 조건

이제 push/pop을 하는 과정에서 고려해야할 조건은 세 가지이다.

1. 스택의 top이 현재 목표로 하는 수보다 작은 경우

   스택의 top이 목표보다 작다면, push를 통해 목표까지 스택을 쌓아나가야 한다.

2. 스택의 top이 현재 목표로 하는 수와 같은 경우

   스택의 top이 목표와 같다면, pop 을 통해 해당 수를 수열에 집어넣는다.

3. 스택의 top이 현재 목표로 하는 수보다 큰 경우

   문제의 실패 조건이다. 스택의 top이 목표로 하는 수보다 큰 경우 해당 수열은 만들 수 없다.

   ex) target : 1 2 5 3 4

   5까지 pop 한 경우의 스택 상황 : 3 4(top)

   목표 : 3

   스택 top > 목표 = 수열 만들 수 없음 .

코드

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

int main(){
    int max;
    cin >> max;

    vector<int> target;
    stack<int> generator;
    vector<char> answer;
    int cur=0;
    int cur_pos=1;
    int target_pos=0;

    int temp;
    for(int i=0;i<max;i++){
        cin >> temp;
        target.push_back(temp);
    }

    while(!(generator.empty() && (cur_pos==max+1))){
        if(generator.empty()){
            if(cur_pos <= max){
            generator.push(cur_pos);
            cur_pos++;
            answer.push_back('+');
            }
        }
        else{
            if(generator.top()==target[target_pos]){
                generator.pop();
                answer.push_back('-');
                target_pos++;
            }
            else if(generator.top()<target[target_pos] && cur_pos <= max){
                generator.push(cur_pos);
                cur_pos++;
                answer.push_back('+');
            }
            else{
                cout << "NO\n";
                return 0;
            }
        }
    }
    for(int i=0;i<answer.size();i++){
        cout << answer[i] << "\n";
    }
}

실행결과