c언어 1874 스택 수열 (백준)

#include <stdio.h>

int main(void)
{
	int n = 0;
	scanf("%d", &n);
	
	int list[n+1]; //input
	int stack[n+1]; //stack 
	char ans[2*n+1]; //'+', '-'
	
	for(int i=0; i<n; i++) {
    scanf("%d", &list[i]); //input
	stack[i] = 0; //초기화
	}
	for(int i = 0; i<=2*n; i++) ans[i]=0; //스택 초기화
	
	int num = 0;
	int p = 0; //stack point
	int i = 0; //list index
	int cnt = 0; //ans index
	while(1)
	{
		if(i==n) { //모든 list의 수를 pop했음
			for(int j = 0; j<cnt; j++)
			printf("%c\n", ans[j]);
			break;
		}
		
		if(num>n) { //불가능 할 경우
			printf("NO");
			break;
		}
		
		if(stack[p] == 0)
		{//num>n 이 될 경우 이는 스택수열의 불가능을 의미한다.
			stack[p] = ++num;
			ans[cnt++] = '+'; //push
		}
		
		if(stack[p] == list[i])
		{
			i++; //다음 list로
			stack[p] = 0; //비교한건 다시 0으로
			ans[cnt++] = '-'; //pop
			if(p>0) p--; //이전 stack으로
		} else p++; //다르다면 다음 stack으로
	}
	return 0;
}

풀이

 

반복문에서 두 개의 과정을 반복한다.

 

1. 스택이 비어있다면(0) 수를 채워 넣는다. //push

2. 입력받은 수와 스택에 있는 수가 같다면 //pop

-다음 입력받은 수로

-스택은 0으로 초기화 후 이전 스택으로 이동한다.

단 다를 경우, 다음 스택으로 이동한다.

 

반복문의 탈출 조건

1. push하는 숫자가 처음 입력받은 n보다 클 경우

-이는 조건을 위배하는 것이므로 NO이다.

 

2. 모든 입력받은 수를 pop 했을 경우 

이는 list index변수인 i가 n이 됐을 때이다.

(i은 0부터 시작)

이 경우엔 +, -을 출력해주면 된다.

 

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

1874번: 스택 수열