백준 1874번(스택 수열) c++

문제

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

1874번: 스택 수열

 

문제 풀이

문제 자체가 조금 이해하기 난해할 수 있다.

 

예제 1번을 풀이를 하자면

 

[4, 3, 6, 8, 7, 5, 2, 1]

최종적으로 이러한 수열을 만들어야 한다.

 

그러면서 오름차순으로 1~8까지 stack에 쌓아야 하는데 push는 어느 때에나 해도 상관없지만 pop은 반드시 저 수열에 맞춰 pop을 해야 한다.

 

+    1

+    2

+    3

+    4

-     4

-     3

+    5

+    6

-     6

+    7

+    8

-     8

-     7

-     5

-     2

-     1

 

스택의 상태는 이렇게 된다.

 

그러면 이런 식으로 코딩을 짜보자.

정해진 수열이 존재하고 오름차순으로 stack에 push를 해야 한다. 그렇다면 이 조건들을 부합하는 경우의 수는 하나밖에 없다라는 이야기다. 복잡하게 생각하지 않아도 된다는 뜻과 같다.

 

먼저 수열의 첫번째 숫자부터 pop하기 위해 4까지 push를 하고 pop한 다음 두번째 숫자를 보자.

3이다 그렇다면 바로 pop을 하면 된다. 세번째 숫자는 6이다. 그러면 5, 6을 push 해주고 pop을 한다.

결국 각 숫자만큼 stack에 push하고 나서 순서에 맞춰 pop을 하면 된다.

만약 pop을 한 뒤 그 pop을 한 숫자보다 낮은 숫자가 나온다면 애초에 이건 만들 수 없는 수열이라는 결과를 우리는 알 수 있다.

 

즉 수학적으로 나타낸다면

Key = 넣어야 하는 숫자

A[i] = 수열의 i번째 숫자

 

Key < A[i] push를 하여 Key == A[i]까지 맞춰주면 된다.

Key == A[i] pop을 하면 된다.

Key > A[i] pop을 하는 순간 주어진 수열 A를 만들 수 없다.

 

 

전체 코드

#include <iostream>

using namespace std;

int stack[100001];
char output[300001];
int nodecnt = 0;

int main(){

ios_base::sync_with_stdio(false);
        cin.tie(0);
	int N;

	cin >> N;

	int key = 0;

	int out_num = 0;

	for(register int i = 0; i < N; i++){

		int input;
		
		cin >> input;
	
		while(key < input){

			key++;
			stack[nodecnt++] = key;
			output[out_num++] = '+';

		}

		if(stack[nodecnt - 1] == input){
			nodecnt--;
			output[out_num++] = '-';
		}
		else{
			out_num = -1;
			break;
		}

	}

	if(out_num == -1){
		cout << "NO\n";
		return 0;
	}

	for(register int i = 0; i < out_num; i++){

		cout << output[i] << '\n';

	}


	return 0;

}