Algorithm

스택_백준_스택 수열_1874

MoYoungmin 2018. 8. 14. 22:36


이 문제는 스택의 성질을 이해해야 하고 시간초과에 유의하여 코드를 짜야한다. Ex) scanf/ printf/ \n를 사용해야된다.

이 코드의 시간복잡도는 O(N) * O(1)이다.






1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <string>
#include <stack>
using namespace std;
 
int main() {
    stack <int> resultStack;
    stack <int> rootStack;
    string result;
    int count;
    int value;
 
    scanf("%d", &count);
    for (int i = count; i >= 1; i--) {
        rootStack.push(i);
    }
    resultStack.push(0); // Initialize
 
    for (int i = 0; i < count; i++) {
        scanf("%d", &value);
 
        while (true) {
            if (resultStack.top() > value) {
                printf("NO\n");
                return 0;
            } // Error
            else if (resultStack.top() < value) {
                result.append("+\n");
                resultStack.push(rootStack.top());
                rootStack.pop();
            } // rootStack -> resultStack. value push
            else {
                resultStack.pop();
                result.append("-\n");
                break;
            } // value print
        }
    }
    cout << result << endl;
    return 0;
}
cs