1874 : 스택 수열

네르기·2021년 9월 5일

생각 스택

알고리즘

목록 보기

43/76

어떤 문제인가?

스택의 push, pop 연산을 활용하는 응용 문제.
시행착오 횟수 : 2번

관찰

어떤 수열이 주어졌을 때, 그 수열을 만들기 위해 필요한 연산 수는, 수열의 길이를 $N$ 이라 할 때 $2N$ 이다.
어떤 수열을 스택만으로 나타낼 수 없는 조건은, 이미 스택 내에서 pop한 원소가 수열 내에 남아있을 때이다.

2가지 해결책을 떠올렸다.
1. 결과값을 배열에 담고, 배열의 크기가 $2N$ 인지 확인. 이상 없으면 결과값들 출력.
2. 특정 원소를 pop했는지 나타내는 배열을 만들고, 이를 이용해 불가능한 수열을 배제한 나머지 수열을 만드는 과정 출력.

1차 시도 : 구상

조건을 다음과 같이 생각했었다. $K_{n}$ 은 수열의 $n$ 번째 원소다.

K_{n} < K_{n+1} < K_{n-1}

다음은 이에 대한 반례다.

4 2 1 3

원소들이 떨어져 있을 경우를 생각하지 못했다.

2차 시도 : WA

조건을 고쳐서 다음과 같이 정했다.

어떤 원소가 지금까지 push한 원소의 최댓값과 pop한 원소의 최솟값 사이에 있으면 그 수열은 스택만으로 나타낼 수 없다.

당연하겠지만 첫 번째 예시에서부터 틀린다. 꼼꼼히 확인하지 못했다.

3차 시도 : AC

관찰에서 언급했듯, 원소가 pop되었는지 나타내는 배열을 생성했고, 다음과 같은 규칙에 따라 추려나갔다.

$K_{n} < K_{n+1}$ 이라면, $K_{n}$ 과 $K_{n+1}$ 만 pop했다고 표시한다.
$K_{n} > K_{n+1}$ 이라면, $K_{n}$ 과 $K_{n+1}$ 을 포함한 그 사이에 있는 수들을 pop했다고 표시한다.
만일 $K_{n}$ 이 이미 pop 되었다면, 그 수열은 생성할 수 없는 수열이다.

#include <stdio.h>

int X[100000], S[100000],k=0,s=0,t=0;
char R[100000];

int main()
{
	int N,i,m=0,j;
	scanf("%d",&N);
	for(i=0;i<N;i++) scanf("%d",&X[i]);
	for(i=1;i<N;i++) {
		if(R[X[i]]) {
			printf("NO");
			return 0;
		}
		R[X[i-1]]=1;
		for(j=X[i-1];j>X[i];j--) R[j]=1;
	} i=0;
	while(i<N) {
		while(k<X[i]) {
			k++;
			S[s++]=k;
			printf("+\n");
		}
		while(S[s-1]>=X[i]){
			s--;
			printf("-\n");
		}
		i++;
	}
}

다른 분들의 풀이

시뮬레이션을 통해서도 풀 수 있다. 내가 보기에 이 방법은 관찰 1.보다 더 간결한 것 같다.

#include <stdio.h>
int main(void)
{
	int n,i,st[100001],top=0,count=0,len=0;
	char ans[200001];
	scanf("%d",&n);
	for(i=0;i<n;++i)
	{
		int a;
		scanf("%d",&a);
		while(count<a)
		{
			st[top++]=++count;
			ans[len++]='+';
		}
		if(st[top-1]==a)
		{
			--top;
			ans[len++]='-';
		}
		else
		{
			printf("NO");
			return 0;
		}
	}
	for(i=0;i<len;++i) printf("%c\n",ans[i]);
	return 0;
}