[ C++ / Stack ] 백준 1874 - 스택수열

Minsu._.Lighting·2023년 11월 9일

🔗 자료구조 / 알고리즘

목록 보기

2/9

📄 문제

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

⌨ 입력

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

💻 출력

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다.
push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

📌 예제

[ Input ]

8
4
3
6
8
7
5
2
1

[ Output ]

+
+
+
+
-
-
+
+
-
+
+
-
-
-
-
-

📝 풀이

핵심

스택의 후입선출 구조만 이해하고 있다면 정말 간단한 문제!

스택의 제일 위로 수열 중 가장 큰 값이 들어온 후에는 스택의 제일 위 원소보다 입력한 숫자가 큰 경우에는 수열을 만들 수 없다는 것 생각!

과정 설명

소스 코드

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

using namespace std;

int iN = 0;

int iCurNumber = 0;
bool bVaild = true;
stack<int> stackNumber;
vector<int> vecNumber;
vector<char> vecAnswer;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> iN;

    for (int i = 0; i < iN; ++i)
    {
        int iNumber = 0;
        cin >> iNumber;
        vecNumber.emplace_back(iNumber);
    }

    stackNumber.push(0);

    for (int i = 0; i < iN; ++i)
    {
        while (stackNumber.top() < vecNumber[i])
        {
            ++iCurNumber;
            stackNumber.push(iCurNumber);
            vecAnswer.emplace_back('+');
        }
        if (stackNumber.top() == vecNumber[i])
        {
            stackNumber.pop();
            vecAnswer.emplace_back('-');
        }
        else
        {
            bVaild = false;
        }
    }

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

    return 0;
}