[백준 알고리즘] 1874번 : 스택 수열

문제

1874번 : 스택 수열

1874번: 스택 수열

내가 작성한 코드 (C++ 성공)

#include <iostream>
#include <string.h>

using namespace std;

int stack[100001];
char res[200001];

int main(){
	int n;
	cin >> n;
	
	int top = 0, istack = 0, ires = 0;
	int num[n+1];
	
	for(int i=0; i<n; i++){
		cin >> num[i];
		
		//cout << "num : " << num[i] << " top : " << top << "\n";
		
		if(num[i] > top) {
			for(int j=top+1; j<=num[i]; j++){
				stack[istack++] = j;
				res[ires++] = '+';
				//cout << "push : " << stack[istack-1] << " +\n";
			}
		} else {
			if(stack[istack-1] != num[i]) {
				cout << "NO\n";
				return 0;
			}
		}
		//cout << "pop : " << stack[istack-1]<< " -\n";
		istack--;
		res[ires++] = '-';
				
		if(top < num[i]) top = num[i];
	}
	
	for(int i=0; i<ires; i++){
		cout << res[i] << "\n";
	}
	
	return 0;
}

 

정리

스택에 대한 문제였는데 사실 STL, vector를 사용하면 금방 해결할 수 있는 문제였다.
하지만 STL 을 사용하지 않고 문제를 풀어보고 싶어서 배열을 이용해서 문제를 풀어보았다.
문제를 보면 엄청 쉽게 느껴졌지만
이 문제를 풀면서 가장 고민을 많이 했던 부분은 숫자를 넣고 빼는 과정이었던 것 같다.

push 와 pop을 하는 과정에서 애먹었던 것 같다.
예를 들어,
1 2 3 4 를 push 하고 4와 3를 차례로 빼고나서
6를 빼려고 할 때 3과 4를 제외한 채 넣고 빼야한다.
그래서 5와 6을 push 하고 6을 pop 해야하는데 이 부분을 어떻게 처리해주야할지 고민을 많이 했던 것 같다.

따라서, 이 문제는 index 와 top을 어떻게 이용하는지에 대한 고민을 해보면 풀 수 있는 문제였다.