[BOJ] 1874 스택수열

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

1874번: 스택 수열

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

stack

 

---------------------------------------------------풀이----------------------------------------------------

 

제목처럼 스택을 이용하는 문제이다.

 

1~n까지 차례대로 들어온다고 생각했을 때, 들어올 차례의 숫자를 num이라고 한다.

만약 입력받은(출력해야 할) 숫자 cur이 num 이상이면, cur까지 스택에 들어와야 하므로

num부터 cur까지 stack에 push한다.

 

만약 cur < num이면, 이미 스택에 있는 숫자이므로

cur이 나올 때까지 pop한다.

이렇게 찾았을 때 cur이 존재하지 않으면, yes_flag가 false가 되고 종료된다.

 

수열이 정상적으로 만들어졌다면 yes_flag는 true이면서 push와 pop의 합의 개수는 2n개다.

각 숫자마다 stack에 push 한 번, pop 한 번 이루어질 것이기 때문이다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>

using namespace std;

int main(void){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    stack<int> s;
    vector<char> ans;
    int num = 1;    // 스택에 들어올 차례인 숫자
    bool yes_flag = true;
    for(int i = 1; i <= n; i++){
        int cur;
        cin >> cur;
        if(cur >= num){
            // push
            for(int i = num; i <= cur; i++){
                ans.push_back('+');
                s.push(i);
            }
            num = cur+1;
            // pop
            ans.push_back('-');
            s.pop();
        }
        else{
            yes_flag = false;
            // pop
            while(!s.empty()){
                ans.push_back('-');
                if(s.top() == cur){
                    s.pop();
                    yes_flag = true;
                    break;
                }
                s.pop();
            }
            if(!yes_flag){
                break;
            }
        }
    }
    if(ans.size() != n*2 || !yes_flag){
        cout << "NO\n";
    }
    else{
        for(int i = 0; i < ans.size(); i++){
            cout << ans[i] << "\n";
        }
    }
    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

다음의 programmers에서 푼 문제와 매우 흡사하다.

https://jyejye311.tistory.com/15

다만, push pop 순서에 따라 +/-를 저장해야한다는 점이 다르다.

문제를 코드가 더럽게 푼 것 같긴 한데, 다듬는건 다음에..!