[백준 / C언어] 1874번: 스택 수열

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

1874번: 스택 수열

 

난이도: solved.ac 실버 2

 

 

스택을 활용하는 문제다

 

문제 이해가 안 되는 분들을 위해 먼저 주어진 예제 1을 통해 설명해 보겠다

 

첫 번째인 4를 만들기 위해서는 스택에서 4를 꺼내야 한다

 

현재 스택은 텅 비어있는 상태이므로 1부터 4까지의 수를 차례로 스택에 넣어준다

 

따라서 ++++가 된다

 

그리고 맨꼭대기에 있는 4를 꺼내면 -가 붙어 ++++-가 된다

 

그다음은 3인데, 이는 현재 스택의 맨 꼭대기에 있는 3을 그대로 꺼내면 되므로 -만 붙어 ++++--가 된다

 

이제 스택에는 1과 2가 있고, 맨 꼭대기에는 2가 있다

 

다음 수인 6을 만들기 위해서는 3, 4, 5, 6을 담아야 한다

 

하지만 3과 4는 이미 사용했으므로 5와 6을 차례로 담아준다

 

따라서 ++가 붙어 ++++--++가 된다

 

그리고 맨 꼭대기에 위치한 6을 꺼내면 -가 붙어 ++++--++-가 된다

 

그다음 수인 8을 만들기 위해서는 현재 스택(1, 2, 5가 남아있음)에 6, 7, 8을 더해서 8을 꺼내야 한다

 

6은 이미 사용했으므로 건너뛰어 7과 8을 차례로 담는다

 

그럼 ++++--++-++가 되고, 8을 꺼내면 -가 붙어 ++++--++-++-가 된다

 

이 과정을 그림으로 나타낸 게 바로 아래의 그림이다

그리고 그다음 수인 7, 5, 2, 1은 현재 남아있는 7, 5, 2, 1을 차례로 pop 시켜주기만 하면 된다

 

따라서 ++++--++-++-에 ----가 붙어 ++++--++-++-----가 완성된다

 

(아래의 그림 참고)

 

예제 2는 수열을 만들지 못하는 경우를 보여준다

 

수열을 만들지 못한다는 건 무엇을 의미할까?

 

아래의 그림처럼 스택의 꼭대기에 있는 수보다 작은 수를 pop 하려고 할 때 수열을 만들지 못하게 된다

스택의 top(꼭대기)에는 3이 있는데, 아래에 있는 1을 꺼내려고 하기 때문이다

 

내 코드에서는 이런 경우가 발생하면 변수 err을 1로 만들어

 

추후 출력할 때 err = 1인 경우에 NO를 출력하도록 해주었다

 

그리고 이미 사용한 수를 파악하기 위해 visited라는 배열을 이용해 모든 원소의 초기값을 0으로 두고 해당 index가 가리키는 수가 사용되면 1로 바꾸어 주었다

 

결과를 출력할 배열은 op이라는 이름의 char형 배열을 사용했는데, 이 +와 -로 이루어진 문자들의 최대 길이는 2*n이다

 

1을 push 하고 바로 pop 하고, 2를 push 하고 바로 pop을 하는 식으로 했을 때 2*n이 된다

 

따라서 여유롭게 op의 크기는 2*n으로 만들어 주었다

 

(내 코드)

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

int main() {
	int n, i;
	scanf("%d", &n);
	int* stack = (int*)calloc(n + 2, sizeof(int));
	int num, top = 0, x = 1;
	int* visited = (int*)calloc(n + 2, sizeof(int));

	char* op = (char*)calloc((n + 1) * 2, sizeof(char));	// 출력물을 저장할 배열
	int op_idx = 0;

	int err = 0;
	for (i = 0; i < n; i++) {
		scanf("%d", &num);
		if (num >= x && !err) {
			while (num >= x) {
				if (!visited[x]) {
					stack[++top] = x;
					op[op_idx++] = '+';
				}
				x++;
			}
			visited[--x] = 1;
			op[op_idx++] = '-';
			stack[top--] = 0;	// 초기화 (top--만 해줘도 상관 없음)
		}
		else if (!err) {
			if (stack[top] != num)	// 스택의 top의 숫자와 다를 때
				err = 1;
			else {
				while (num < x)	x--;
				visited[x] = 1;
				op[op_idx++] = '-';
				stack[top--] = 0;	// 초기화 (top--만 해줘도 상관 없음)
			}
		}
	}
	if (err)
		printf("NO");
	else {
		for (i = 0; i < op_idx; i++)
			printf("%c\n", op[i]);
	}
	return 0;
}