[BOJ/C++] 스택 수열(1874번)

1. 개요

https://www.acmicpc.net/problem/1874

1874번: 스택 수열

1-1. 설명

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

1-2. 제한 사항

 - 첫 줄에 n이 주어지며, n은 1 이상 100,000 이하의 자연수

 - 둘째 줄부터 n개의 줄에는 수열을 이루는 1 이상 n 이하의 정수가 주어짐

 - 같은 정수가 두번 나오는 일은 없음

---

2. 구현

2-1. 풀이

메모리 풀을 이용해 스택과 결과를 저장하는 배열을 생성하고, 입력값과  stack의 top 값이 동일하면 pop, 동일하지 않으면 push를 해준다. 마지막 조건으로 stack에 숫자가 남아있으면 NO가 뜨고 숫자가 남아있지 않으면 결과를 저장하는 배열이 출력된다. 

2-2. 소스 코드

#include <iostream>
using namespace std;

constexpr size_t MAX_NUM = 100000;
constexpr size_t MAX_CHAR = 200000;
int stack[MAX_NUM];
char result[MAX_CHAR];

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

    int n, input, top = 0, resultIdx = 0, index = 1;
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> input; 

        while (true) {
            if (input == stack[top - 1]) { // stack top의 숫자와 input 값이 동일할 때
                result[resultIdx++] = '-'; // pop
                --top;
                break;
            }
            else if (input != stack[top - 1] && index <= n) { // stack top의 숫자와 input 값이 동일하지 않을 때
                result[resultIdx++] = '+'; // push
                stack[top++] = index++;
            }
            else break; // index가 n을 넘어갈 때
        }
    }
    if (top != 0) cout << "NO"; // stack에 숫자가 남아있을 때
    else { // 없을 때
        for (int i = 0; i < resultIdx; i++) {
            cout << result[i] << "\n";
        }
    }
    return 0;
}