[알고리즘/문제풀이/BOJ 1874번] 스택 수열

스택 수열 문제는 스택으로 입력으로 주어지는 수열을 만들 수 있는지 확인하며 그렇다면 push, pop의 순서를 출력하는 문제이다. 이 문제를 풀기 위해 스택을 선언하였으며, 문제에서 주어진 입력을 단서로 삼아 push, pop의 사용 여부를 조사하였다. n까지의 자연수가 오름차순으로 스택으로 입력되므로 스택에 입력된 숫자의 가장 큰 값이 입력으로 받아진 숫자보다 작다면 스택에 push를 한 후 pop을 하고, 크다면 기존에 스택에서 pop을 하여 입력된 숫자를 출력하는 지 확인해야 한다.

즉 어느 시점에서 스택을 활용하여 숫자를 출력하기 위해서는 다음과 같은 두 가지 방법 중 하나를 선택해야 한다는 사실을 이용해야 한다.

1. 오름차순으로 정렬된 순열의 숫자를 차례로 스택에 push한 후 1개의 숫자를 pop하는 것

2. 기존의 스택에 있던 최상위의 숫자 1개를 pop하는 것

숫자가 스택에 오름차순으로 들어간다는 사실은 입력된 숫자가 출력되기 위해 어떠한 방법을 선택해야 하는지 알려준다. 추측한 방법을 통해 입력된 숫자를 스택을 통해 출력할 수 있다면 다음 입력된 숫자로 넘어가고, 그렇지 않다면 해당 수열은 스택을 통해 만들어낼 수 없는 수열이므로 NO를 프린트하고 프로그램을 종료한다. 모든 수열이 확인 작업을 통과하였다면 미리 저장한 push, pop 순서를 출력한다.

주의할 점은 숫자는 100000이지만 숫자가 출력되기 위해서는 push, pop 1쌍이 필요하므로 이를 저장하기 위해서는 200000개의 공간이 필요하다.

작성한 코드는 다음과 같다.

---

#include<stdio.h>
//https://ark-hive.tistory.com/
int n, temp;
int stack[100020];
char operation[200020];
int top;
int next = 1;
int op;
//temp 입력 -> 수열 검색 위치와 비교
//검색 위치보다 temp가 크거나 같으면 스택에 temp까지 저장 후 pop
//작으면 출력될 숫자가 스택에 있으므로 스택에서 pop

//스택으로 숫자 만들기
//1. 일정 숫자까지 스택에 넣은 다음 pop
//2. 스택에 있던 기존의 숫자에서 pop

void push(int num){
	top += 1;
	stack[top] = num;
}

int pop() {
	if (top == 0) return -1;
	else {
		top -= 1;
		return stack[top + 1];
	}
}

int main(void) {
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf("%d", &temp);
		if (temp >= next) {
			for (; temp >= next; next++) {
				push(next);
				operation[op++] = '+';
			}
			pop();
			operation[op++] = '-';
		}
		else if (temp < next) {
			if (pop() != temp) {
				printf("NO\n");
				return 0;
			}
			else {
				operation[op++] = '-';
			}
		}
	}

	for (int i = 0; i < op; i++) {
		printf("%c\n", operation[i]);
	}

	return 0;
}

문제의 지문은 다음 링크에서 확인할 수 있다.

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