[백준] 1874번 - 스택 수열 (C언어) [Silver2]

intput	output
8 4 3 6 8 7 5 2 1	+ + + + - - + + - + + - - - - -

해당 문제는 스택 자료구조 개념을 알고 문제에서 원하는 바를 이해 한다면 충분히 해결 가능한 문제이다.

 

문제 해결 과정은 다음과 같다.

1. N 만큼 입력 받는다.
2. 1부터 N까지의 수를 조합하여 목표 수열을 만든다.(단, 중복 제외)
3. 수열은 push 와 pop 연산을 사용하여 확인한다.
4. 두 연산으로 목표하는 수열이 있는지 확인한다.
5. 두 연산으로 표현할 수 없다면 "NO"를 출력한다.

Last In First Out 특성을 사용하여 오름차순 스택은 3가지 경우로 나뉘어 문제 해결이 가능하다.

1. 스택의 상단 수가 목표 수 보다 낮은 경우 push
2. 스택 상단 수가 목표 수와 같은 경우 pop
3. 스택의 상단 수가 목표 수 보다 큰 경우 NO

전체 소스 코드는 아래와 같다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 100000
#pragma warning(disable:4996)
int stack[SIZE]; // 스택
char c[SIZE * 2]; // +,- 저장할 char형 배열
int top = -1; // 스택 상단 표시
int arr[SIZE];
int main() {
	int n;
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}

	int arr_index = 0; // 할당한 배열 인덱스
	int c_index = 0; // + , - 표현 인덱스
	int temp = 1;

	while (1) {
		// 스택의 상단 수가 해당 배열 인덱스 수 보다 낮은 경우 push
		if ((top == -1) || (stack[top] < arr[arr_index])) {
			stack[++top] = temp++;
			c[c_index++] = '+'; // push = '+'
		}
		/* 스택의 상단 수가 해당 배열 인덱스 수와 같은 경우 pop */
		else if (stack[top] == arr[arr_index]) {
			top--;
			c[c_index++] = '-';
			arr_index++;
		}
		else { /* 스택의 상단 수가 해당 배열 인덱스 수보다 큰 경우*/
			printf("NO\n");
			return 0;
		}
		if (c_index == n * 2) // 무한 루프 탈출
			break;
	}
	
	
	for (int i = 0; i < c_index ;i++)
		printf("%c\n", c[i]);

	return 0;
}

 

[1874번]

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

1874번: 스택 수열

 

[github]

https://github.com/MinWook6457

MinWook6457 - Overview