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

문제

---

문제에 대한 링크는 여기를 클릭해주세요.

문제 설명

---

1부터 n까지 차례대로 push또는 pop을 하여 입력한 수열과 똑같은지 비교하는 문제입니다. 즉 43을 만들기 위해 1부터 4까지는 push를 하고 pop을 2번 진행하면 됩니다. 이러한 진행 상황을 push는 '+', pop은 '-'으로 출력합니다.

풀이

---

1부터 차례대로 push를 하고 push를 한다는 '+'기호는 vector에 push_back합니다. 그리고 수열과 같은 수가 나타나면 즉시 pop을 하여 꺼내고 다음 수를 비교합니다. 이 점을 반복문으로 구현하였고, 스택이 비어있을 때 vector에 있는 요소들을 출력합니다. n이 될 때까지 진행하면서 비어있지 않는다는 뜻은 수열을 만들 수 없다는 뜻이 됩니다.

소스 코드

---

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

using namespace std;

int main()
{
    stack<int> s;
    vector<char> v;
    int n, idx(0);

    cin >> n;
    int *arr = new int[n];

    for (int i = 0; i < n; i++)
        cin >> arr[i];

    for (int i = 1; i <= n; i++)
    {
        s.push(i);
        v.push_back('+');

        while (arr[idx] == s.top())
        {
            s.pop();
            v.push_back('-');
            idx++;

            if(s.empty())
                break;
        }
    }

    delete[] arr;

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

    return 0;
}

주의 사항

---

반드시 while문 안에 if문으로 empty로 스택이 비어있는지 체크해야합니다. while문에 !s.empty()를 &&로 엮을 시 오류가 발생합니다. 또한 endl 대신 '\n'으로 줄바꿈을 해야합니다. endl은 내부 버퍼까지 비우는 작업을 하기 때문에 시간 초과가 발생합니다.