백준 1874 스택수열

문제를 처음 접하고 20분동안 머리를 굴려봤지만 도대체 무슨 말을 하는지 이해를 못했었다. 구글링을 한 뒤 문제의 의도를 파악했다.

이해한 바를 정리해보자면
정수 N을 처음에 입력받고, 이후에 N개의 정수를 입력받는다.
(이 N개의 정수가 출제가가 만드려는 수열이다.)
그리고 N개의 수를 1부터 N까지 오름차순으로 스택에 저장을 하는데
두 번째 출력부터 받는 정수를 스택에서 pop해주는 것이다.
pop은 '-'를 출력해준다.
해당하는 수가 없으면 pop할 수 있을 때까지 다시 오름차순으로 push해준다.

이 모든 과정이 정상적으로 수행이 되면 +와 -를 순서대로 출력해주고
중간에 문제가 생기면 NO를 출력한다.

말로 하니 이해가 잘 안될 수 있다.
내가 본 블로그 글을 인용하겠다.
(출처)
https://organize-study.tistory.com/60

예제를 보면 수열 {4 3 6 8 7 5 2 1} 을 만들 수 있는지 물어본다.

s에 예제 출력대로 한다고 하면

s = {1}

s = {1,2}

s = {1,2,3}

s = {1,2,3,4}

s = {1,2,3} resultt = {4}

s = {1,2} result = {4,3}

s = {1,2,5}

s = {1,2,5,6}

s = {1,2,5} result = {4,3,6}

s = {1,2,5,7}

s = {1,2,5,7,8}

s = {1,2,5,7} result = {4,3,6,8}

s = {1,2,5} result = {4,3,6,8,7}

s = {1,2} result = {4,3,6,8,7,5}

s = {1} result = {4,3,6,8,7,5,2}

s = {} result = {4,3,6,8,7,5,2,1}

문제를 이해하니 쉽게 구현이 되었다.

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


int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N;
    stack<int> S;
    vector<char> V;   
    cin >> N;
    int i = 1;
    while(N--) {
        int a;
        cin >> a;
        if(a >= i) {
            for(; i <= a; i++) {
                S.push(i);
                V.push_back('+');
            }
            S.pop();
            V.push_back('-');
        } else {
            if(a == S.top()) {
                S.pop();
                V.push_back('-');
            } 
            else if(a <= S.top()) S.pop();
            else {
                cout << "NO";
                return 0;
            }
        }
    }
    for(char a : V) cout << a << '\n';
}

아래에는 더 간결하고 좋은 코드
벡터가 아닌 string으로 +와 -를 출력해주니 더 좋은 것 같다.

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


int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N;
    stack<int> S;
    string ans;
    cin >> N;
    int i = 1;
    while(N--) {
        int a;
        cin >> a;
        while(a >= i) {
            S.push(i++);
            ans += "+\n";
        }
        if(S.top() != a) {
            cout << "NO";
            return 0;
        }
        S.pop();
        ans += "-\n";
    }
    cout << ans;
}