백준 1874번, 스택 수열

백준 1874번 c++ 문제풀이

문제: 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

풀이:

1. 입력 받은 숫자가 푸쉬해야 되는 숫자 보다 크다면, 그 차이 만큼 push하구 pop한다.
2. 입력 받은 숫자가 스택의 top 부분에 있다면 바로 pop한다.
3. 입력 받은 숫자가 스택의 top 부분보다 작다면 수열을 만들수 없다. no 출력
   이유: 일단 스택에 있다는 소리는 아직 입력 받은 숫자가 아니라는 뜻, 스택의 top보다 작은 수를 입력하면 아직 입력 받지 않은 값들도 차례대로 pop을 해야하는데, 그렇게 되면 나중에 그 수(미리 pop한 수)를 입력 했을 때 스택에 존재하지 않아 수열을 만들 수 없게 된다.

코드:

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    
    int n;
    int num;
    int start = 1;
    stack <int> s;
    vector <char> v1;

    cin >> n;
    
    

    for(int i=1;i<=n;i++){
        cin >> num;
        if(start<=num){
        for(int i=start;i<=num;i++){
            s.push(i);
            start+=1;
            v1.push_back('+');
        }
        s.pop();
        v1.push_back('-');
        }else if(!s.empty() && s.top() == num){
            s.pop();
            v1.push_back('-');
        }else if(!s.empty()&& s.top() > num){
            cout << "NO";
            return 0;
        }
    }

    for(int i=0;i<v1.size();i++){
        cout << v1[i] << "\n"; //시간초과 난 이유 endl 써서, 다음 부터는 "\n" 쓰자
    }
    
    return 0;
}

문제를 알맞게 푼거 같은데 제출하면 계속 시간 초과가 나서, 한참 헤멨던 것 같다.
이유는 마지막에 출력할 때 endl을 썼기 때문이었다. endl은 검사를 진행하기에 “/n”보다 시간이 오래걸린다.