(매일 BOJ) C++ 1874번 스택 수열

이번 문제는 실버 2 난이도의 1874번 스택 수열이다.

문제 요약

• 1부터 N까지 오름차순으로 스택에 숫자를 넣고(push), 뽑아내(pop)면서 원하는 수열을 만들어야 함
• 만들 수 있는 수열이면 +, - 연산을 출력하고, 불가능하면 NO 출력

접근법

입력 수열을 왼쪽부터 차례로 만들어야 함

• ex) 입력: 4 3 6 8 7 5 2 1
• 스택에는 오름차순 숫자만 넣을 수 있음 >> 백터로 입력 수열을 받는다.

"현재 스택의 top"이 목표 수열의 숫자와 일치할 때 pop

• 아직 목표 숫자가 스택에 없으면 → 숫자를 push하면서 채움
• 스택 top이 입력 숫자와 같으면 → pop
• 더 큰 수가 필요하면 계속 push (1부터 N까지 오름차순이기 때문)
• 더 작은 수인데 이미 pop된 숫자라면? → NO 출력

아래는 작성한 코드이다.

# include <bits/stdc++.h>
using namespace std;


int main(void){
    ios::sync_with_stdio(0); cin.tie(0);
    int N;
    cin >> N;
    vector<int> final;
    stack<int> s;
    vector<char> result;
    int temp = 1;
    for (int i  = 0; i < N; i++){
        int a;
        cin >> a;
        final.push_back(a);
    }

    for(int i = 0; i < N; i++){
        int a = final[i];

        while(temp <= a){
            s.push(temp);
            result.push_back('+');
            temp += 1;
        }

        if(s.top() == a){
            s.pop();
            result.push_back('-');
        }
        else{
            cout << "NO" << '\n';
            return 0;
        }
    }
    for (int i = 0; i < result.size(); i++){
        cout << result[i] << '\n';
    }
}