(BOJ) 1874 풀이

#include<bits/stdc++.h>
using namespace std;
stack<int> s;
int main(void){
    ios::sync_with_stdio(0);cin.tie(0);
    int N,n,c=1;
    string ans;
    cin >> N;
    while(N--){
        cin >> n;
        while(c<=n){
            s.push(c++);
            ans+="+\\n";
        }
        if(s.top()==n){
            s.pop();
            ans+="-\\n";
        }else{
            cout << "NO" << '\\n';
            return 0;
        }
    }
    cout << ans;
}

이해하는데에 조금 오래걸렸던 문제입니다.

1부터 n 까지의 수를 차례대로 스택에 넣으면서, 뺏을 때의 값을 가지고 수열을 만드는데

빼고난 뒤에도 값을 넣을 수 있지만 아까와 같이 오름차순으로 넣어야한다.

(4까지 넣고 4를 뻈으면, 5부터 넣기 시작)

c 는 하나씩 증가할 뿐 감소하지 않기 떄문에 출력되는 +/- 는 각각 n 개가 됩니다.

4,3,6,8,7,5,2,1

test case 를 예를 들어 설명하면, 먼저 c 를 5까지 증가시키면서 스택에 4까지 넣고,

4 를 pop 한 뒤, 다음 수가 5보다 작으므로 스택에 값을 추가하지 않고

스택의 최상단값이랑 비교해서 맞으면 pop 합니다.

스택에 추가하는 과정을 마치고 최상단값과 다음 수가 같지 않다면

그것은 잘못된 수열이므로 NO 를 출력하고 리턴(혹은 종료)

 

다음 수 → 6 , c 를 5부터 6까지 넣고 pop, (c==7)

다음 수 → 8 , c 를 7부터 8까지 넣고 pop, (c==8)

그러면 스택에는 1,2,(3,4),5,(6,8),7 이 값들이 남아있습니다. (왼쪽이 bottom, 괄호친 수는 pop 된 수)

이제 c==n+1 이 되었으니, 더이상의 추가는 없고 스택을 하나씩 pop 하면서 나머지 수열과 비교하게 됩니다. 차례대로 pop 하면 7,5,2,1 일테니 올바른 수열입니다.

지금까지 push/pop 할 때마다 ans 에 +/- + ‘\\n’ 추가한 것을 출력해주면 됩니다.