BOJ 1874 스택 수열

문제

뭐 대략 이런 문제이고 읽어봤을 때 딱히 어렵다고 느껴지지는 않는(?) 느낌이다 ㅎㅎ,,,

처음에는 두가지 풀이법을 생각을 해봤다. 먼저 1~N 까지 쌓아놓고 연산을 하는 것이다. 예를 들어 1~N까지 오름차순으로 저장된 배열을 만들고 그 안에서 수열에 있는 수를 순회하면서 이런저런 연산을 하는 그런 방식(...?) 이었는데... 일단 문제 이름부터가 스택 수열이니까 스택을 사용하는 방법으로 다시 생각해봤다.

풀이 순서를 대략적으로 정리해보면 아래와 같다.

1. 수열을 순회하면서 쌓아야되면 쌓고, 빼야 되면 뺀다. (미리 생성한 스택 사용)
2. 빼야 되는데 못빼는 상황이 생기면 NO 출력
3. 수열을 전체 다 순회하고 끝나면 결과 출력(결과를 중간 과정에서 출력하면 NO와 같이 나올 수 있으므로 마지막에!)

그렇게 완성된 코드는 아래와 같다.

#include <iostream>
#include <vector>

using namespace std;

int N;
int current;

int Narray[100000];
vector<int> stack;
vector<char> printstack;

void input();

int main() {
    input();
    current = 1;

    for(int i=0;i<N;i++){
        // 스택이 비어있으면 쌓는다
        if(stack.empty()){
            for(int j=current;j<=Narray[i];j++){
                stack.push_back(j);
                printstack.push_back('+');
            }
            stack.pop_back();
            printstack.push_back('-');
            current = Narray[i]+1;
        }
        else {
            if(stack.back() == Narray[i]) {
                stack.pop_back();
                printstack.push_back('-');
            }
            else {
                if(stack.back() > Narray[i]) {
                    cout << "NO";
                    return 0;
                }
                else {
                    for(int j=current;j<=Narray[i];j++){
                        stack.push_back(j);
                        printstack.push_back('+');
                    }
                    stack.pop_back();
                    printstack.push_back('-');
                    current = Narray[i]+1;
                }
            }
        }
    }

    vector<char>::iterator iter;
    for(iter = printstack.begin();iter != printstack.end();iter++){
        cout << *iter << "\n";
    }

    return 0;
}

void input() {
    cin >> N;
    for(int i=0;i<N;i++){
        cin >> Narray[i];
    }
}

코드가 간단해서 뭐 설명할 것은 없을 거 같고 약간 마지막에 헤맨 부분이 저 printstack을 출력하는 과정이었는데 이상하게 계속 시간초과가 떠서 이유를 찾다 찾다 저 마지막 "\n"을 endl에서 바꿔봤는데 맞았다고 한다.... 아무래도 endl 이 좀 시간을 잡아먹는 뭔가가 있는거 같은데 이거는 좀 알아봐야 될거 같다 ㅎㅎ