1874 스택수열

처음엔 문제를 이해하기가 좀 어려울 수 있다.

어떤 스택 s에 1,2,3,4,5,,,,n까지 차례대로 집어넣을 수 있다.

이 때 s에서 pop한 수로 수열을 만들었을 때 문제에서 제시한 수열 t를 만들 수 있으면 만드는 순서를 출력하고, 아니면 NO를 출력하는 문제다.

예제를 보면 수열 {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}

이 되기 때문에 "result = t"가 만족하므로 순서대로 출력하면 된다.

풀이는 의외로 간단하다.

현재 s에 들어가야 할 수를 i라고 하고 t에서 k번째 수를 result에 집어넣어야 할 때 i <= t[k] 라면

i<=t[k]인 동안 s에 i를 push 해준다. 그리고 s.top() == t[k]라면 pop해주고, 이 두경우에 속하지 않으면 표현이 불가능 하므로 NO를 출력한다.

무슨 말이냐 하면 예제에서 t의 첫번째 수인 t[1]은 4이다. 그리고 초기 상태에는 i가 1이므로

i<=4인 동안, 즉 1,2,3,4를 s에 push 해준다. 그 다음에는 s.top() == 4 == t[1] == 4 이므로 pop해준다. NO가 나오는 조건은 설명하자면 이렇다.

t = {4 2 6 8 7 5 3 1} 인 경우 처음 4는 무사히 출력이 되지만 그 다음 2를 출력하려면 3을 먼저 꺼내야 하므로

result = {4,3,2}가 될 수밖에 없다. 이럴때 NO를 출력한다.

<코드>

#include <algorithm>
#include <stdio.h>
#include <stack>
#include <queue>
using namespace std;
 
int n, temp;
queue<int> q;
stack<int> s;
queue<char> ans;
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &temp), q.push(temp);
    int l = 1;
    while (q.size()) {
        if (s.size() && s.top() == q.front()) {
            s.pop();
            q.pop();
            ans.push('-');
        }
        else if (l <= q.front()) {
            while (l <= q.front()) {
                s.push(l++);
                ans.push('+');
            }
        }
        else {
            printf("NO");
            return 0;
        }
    }
    while (ans.size()) printf("%c\n", ans.front()), ans.pop();
    return 0;
}