[01874] 스택 수열

[01874] 스택 수열

문제

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

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

입력

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

출력

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

코드

#include <iostream>
#include <vector>

using namespace std;

/* 조건 */
#define MAX_N 100000

/* 변수 */
int N, tmp;
int start = 1;
bool flag = true;
vector<int> stack;
vector<bool> result;

/* 함수 */

int main() {
    /* 입력 */
    cin >> N;

    /* 풀이 */
    for(int i = 0; i < N; i++) {
        cin >> tmp;
        if(start <= tmp) {
            for(int j = start; j <= tmp; j++) {
                stack.push_back(j);
                result.push_back(true);
                start = j+1;
            }
            stack.pop_back();
            result.push_back(false);
        } else {
            if(stack.back() == tmp) {
                stack.pop_back();
                result.push_back(false);
            } else {
                flag = false;
                break;
            }
        }
    }

    /* 출력 */
    if(flag) {
        for(int i = 0; i < N * 2; i++) {
            cout << (result[i] ? "+\n" : "-\n");
        }
    } else {
        cout << "NO\n";
    }
}

풀이

논리

• stack에는 1부터 넣기 시작한다.
  (start로 다음에 넣을 숫자 keep)

• 이 때 입력받은 숫자(input)보다 start가 작은 경우, 입력받은 숫자까지 push 후 pop
  --> input이 수열에 추가된다.

• input보다 start가 큰 경우 stack에 있어야 수열에 추가 가능
  그러나, stack은 top에서 pop 할 수 밖에 없으므로 top이 input과 다르면 불가능

• top이 input과 같다면 pop으로 수열에 추가

• 위의 과정을 N회 반복하여 모든 input에 대하여 반복한다.

출력

• flag로 가능 여부를 확인
• 가능한 경우(falg가 true) result에서 0부터 $N*2$ 까지 출력
  • N개의 입력에 대하여 모두 Push와 Pop 한번씩 총 2번의 연산을 하므로 $N * 2$회
  • true는 +, false는 - 출력
• 불가능한 경우(flag가 false) NO 출력

출처

백준 [01874] 스택 수열
https://www.acmicpc.net/problem/1874