[백준 / C++] 1874번: 스택 수열

문제 링크

1874번: 스택 수열

---

문제

---

문제 설명

사용자가 입력한 1부터 n까지의 수열이 있다.

스택 내에서 push와 pop으로 넣었다 뺏다 하면서 그 수열과 같게 만들어야 한다.

만약 수열이 안 만들어지면 NO를 출력한다.

---

코드

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

#include <cmath>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int N; cin >> N;
    int num, numArr[100000], stackNum = 1, wrong = 0;

    stack <int> seq;
    seq.push(0);

    vector <char> sign; sign.reserve(N);
    vector <int> numSeq; numSeq.reserve(N);

    for (int i = 1; i <= N; i++) {
        cin >> num;
        numArr[i - 1] = num;

        while (seq.top() < num) {
            seq.push(stackNum);
            sign.push_back('+');

            stackNum++;
        }

        if (seq.top() == num) {
            numSeq.push_back(seq.top());
            if (numArr[i - 1] != numSeq[i - 1]) wrong = 1;

            seq.pop();
            sign.push_back('-');
        }

    }

    if (wrong == 1) cout << "NO";
    else {
        for (int i = 0; i < sign.size(); i++) {
            cout << sign[i] << '\n';
        }
    }

    return 0;
}

---

문제 풀이

사용자가 숫자를 입력한다. 그 숫자를 numArr라는 배열에 저장한다.

사용자가 입력하는 수 num보다 스택의 최상위 숫자(top)이 작다면 1부터 num에 해당하는 수까지 스택에 넣는다. (push)

스택의 최상위 숫자(top)와 입력한 수 num이 같다면 vector 컨테이너 numSeq에 저장한 뒤 스택에서 삭제(pop)한다.

• numSeq에 저장해주는 이유는 나중에 [numArr] 배열과 비교하기 위해서이다.
• 비교를 통해 사용자 입력값과 다르다면 wrong 변수를 1로 초기화해준다.

모든 입력이 끝나고 wrong 변수가 1이라면 NO를 출력한다.

아니라면 push할 때와 pop할 때 넣어준 +, - 기호를 출력한다.

---

시간 초과

입력값이 최대 10만이면서 반복 횟수도 많기 때문에 시간 초과가 날 수 있다.

이를 방지하기 위해

ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

를 main함수 바로 아랫줄에 작성해준다. 이를 작성하면 C의 stdio과 C++의 iostream 사이의 동기화를 해제할 수 있다.

또 cin과 cout 사이의 묶임을 풀어주어 순서를 없애줄 수 있다.

마지막으로 개행문자를 쓸 때 endl 대신 \0을 사용해서 개행에 딜레이를 줄일 수 있다.