백준 1874 스택 수열 [C++]

문제 링크 : https://www.acmicpc.net/problem/1874

소스코드 

#include <iostream>

#include <stack>

#include <vector>

using namespace std;

int main() {

    int n;

    vector<int> v;

    stack<int> s;

    vector<char> d;

    cin >> n;

    for (int i = 0; i < n; ++i) {

        int k;

        cin >> k;

        v.push_back(k);

    }

    vector<int>::iterator it;

    it = v.begin();

    for (int i = 1; i <= n; ++i) {

        s.push(i);

        d.push_back('+');

        while (!s.empty()) {

            if (*it != s.top()) break;

            else {

                s.pop();

                d.push_back('-');

                ++it;

            }

        }

    }

    if (s.empty()) {

    for(int i=0 ;i<d.size() ; ++i)

        cout<<d[i]<<"\n";

    }

    else cout << "NO";

}

숫자를 하나씩 입력받으면서 스택에 푸쉬합니다.

푸쉬를 하면서 미리 저장한 수열 배열 인덱스에 있는 값과 같으면 팝하고, 배열을 다음 인덱스로 넘깁니다.

마지막 숫자가 팝되고 나서는 스택에서 차례로 팝하면서 배열에 있는 값과 같아야 합니다.

만약 다르다면 그 수열은 만들 수 없는 수열입니다.

주의 ! 이 문제는 출력이 많아 endl로 출력하면 시간초과가 걸립니다. 대신 \n 로 개행해 주시면 해결됩니다.

( endl은 개행 후 버퍼 제거까지 하기 때문에 시간이 더 걸립니다.)