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

 

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

사용 언어: C

 

문제

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

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

입력

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

출력

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

 

우선 문제의 이해부터가 우선이었기에 이해를 하는데만 1시간 걸렸다;; (난 바본가 ㅠㅠ)

이해를 하고 나서는 문제를 푸는 방법을 세 가지를 강구했었다.

 

첫 번째 풀이

첫째로는, 숫자 n을 입력받으면 (ex:n=8) 그와 관련된 모든 가능한 수열을 계산해서 이 결괏값 중 내가 입력한 수열과 일치하면 그 수열을 출력하고 그중에 없으면 NO를 출력하는 것이었다.

근데 생각해보니 숫자 n이 100,000까지 가는데 n=100,000이면 2^100,000 개의 가능한 수열을 계산해야 하는데 이게 슈퍼컴퓨터면 모를까 가능할 리가..^^

 

두 번째 풀이

둘째로는, 숫자를 하나씩 입력받아서 수열이 만들어지는지 안 되는지 확인하는 방법이다.

설명은 코드와 함께 //로 설명을 최대한 했으므로 부가 설명은 필요 없다고 생각한다.

//숫자를 하나씩 스캔 받아서 차례차례 수열이 만들어지는지 안 되는지 확인하는 풀이 

#include <stdio.h>
#define MAX 100000

int main(void)
{
	int i,n,k,stkIdx=0,resIdx=0,max=0;
	int stack[MAX];
	char res[MAX*2];
	scanf("%d",&n);
	while(n--) //while(0)이 되면 바로 멈춤
	{
		scanf("%d",&k);
		if(k>max)
		{
			for(i=max;i<k;i++)
			{
				stack[stkIdx++]=i+1; //스택 쌓기
				res[resIdx++]='+'; // '+' 저장
			}
			max=k; 
		}
		
		//k<max인 경우 stack[stkIdx]의 바로 전 경우가 k와 일치하지 않는 이상 수열을 만들 수 없음
		//stack[stkIdx-1]!=k 이면 max와 입력한 수 사이의 출력 안한 숫자가 있다는 뜻
		else if(k<max && stack[stkIdx-1]!=k) 
		{
			printf("NO\n");
			return 0;
		}
		
		//k==max
		stkIdx--; //한 숫자의 push들이 끝나면(+를 다 입력하면), 항상 pop이 일어나야함.
		res[resIdx++]='-'; //마찬가지로 항상 pop하면서 '-' 출력.
	}
	
	for(i=0;i<resIdx;i++)
		printf("%c\n",res[i]);
	return 0;
}

 

세 번째 풀이

셋째로는, 숫자들을 한 번에 입력받아서 arr[]에 넣은 다음 stack[]을 쌓아가면서 비교하는 방법이다.

두 번째 풀이와 마찬가지로 부가 설명은 안하겠다.

//숫자를 한번에 스캔 받아서 arr에 넣은 다음 arr와 stack을 비교해가면서 결과를 도출
//stack[top]이 arr[idx] 보다 낮으면 push, 같으면 pop, 크면 "NO"

#include <stdio.h>
#define MAX 100000

int stack[MAX];
char res[MAX*2];
int top=-1;

int main(void)
{
	int n,num=0,idx=0,res_idx=0;
	scanf("%d",&n);
	int arr[n];
	for(int i=0;i<n;i++)
		scanf("%d",&arr[i]);
	int k=n*2;
	while(k--) //while(0)이 되면 바로 멈춤
	{
		//stack[top]이 arr[idx]보다 낮은 경우 (push)
		if(top==-1 || stack[top]<arr[idx])
		{
			stack[++top]=++num; //push
			res[res_idx++]='+';
		}
		
		//stack[top]이 arr[idx]와 같은 경우 (pop)
		else if(stack[top] == arr[idx])
		{
			top--; //pop
			res[res_idx++]='-';
			idx++; //배열의 다음 숫자로 넘어감
		}
		
		//stack[top]이 arr[idx]보다 큰 경우 ("NO")
		else
		{
			printf("NO"); //수열을 만들 수가 없음
			return 0;
		}
	}
	
	for(int i=0;i<res_idx;i++)
		printf("%c\n",res[i]);
	return 0;
}

느낀 점

 

BOJ 10828번:스택보다는 확실히 문제가 직관적이지 않아서 문제를 이해하고 풀이를 구현하는 데에 있어서 꽤 오랜 시간이 걸려서 푸는데 꽤 힘들었다. 어려운 문제일수록 백준에서 제공하는 예제 입력과 예제 출력을 보면서 규칙을 찾아내고 그것을 어떻게 구현할 것인지 생각하는 게 무작정 풀려고 하는 것보다 확실히 중요한 것 같다.