[Baekjoon] Class2 07 - 스택 수열 [1874]
스택 수열 [1874번]
스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.
1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.
입력
첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.
출력
입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.
생각해볼점
스택(Stack)
위키피디아 링크
자료의 입력과 출력을 모두 자료의 끝에서밖에 할 수 없는 구조이다.
즉, 자료가 입력되면 현재 남아있는 자료의 맨 끝에 들어와 순서대로 쌓인다.
반대로 자료를 출력할때는 맨 끝에 남아있는 자료, 다시말해 가장 마지막에 들어온 자료밖에 출력할 수 없다.
이 문제의 경우
문제가 조금 헷갈릴 수 있는데, push할 때마다 숫자가 1부터 순서대로 스택에 입력되고 pop을 하면 스택에서 데이터를 출력해 우리가 만들 배열로 집어넣는다. 물론 이 때 출력되는 자료는 스택에 쌓여있던 맨 마지막 데이터이다.
예를들어 문제에 예시로 나와있던 43687521이라는 배열을 만들기 위해서는
- 배열의 가장 첫 원소인
4를 만들기 위해 네번push한다. 스택에는1234가 쌓인다. pop으로 스택의4를 가져와 배열에 집어넣는다. 한번 더pop으로 이번엔3을 가져온다.- 다음 원소인
6을 만들기 위해 다시push한다. 스택에는1256이 쌓인다. pop으로6을 배열로 빼고, 그 다음인8을 만들기 위해 또다시push한다. 스택에는12578이 쌓인다.- 다섯번의
pop으로8,7,5,2,1을 연달아 배열로 집어넣는다.
코드 구현
#include <stdio.h>
#include <stdlib.h>
int main()
{
int num, idx, stack_idx = -1, push_count = 0, push_pop_idx = 0;
int *arr, *stack, push_pop[200000];
scanf("%d", &num);
arr = (int *)malloc(num * sizeof(int));
stack = (int *)calloc(num, sizeof(int));
idx = -1;
while (++idx < num)
scanf("%d", &arr[idx]);
idx = 0;
while (idx < num)
{
if (stack[stack_idx] < arr[idx]) // 배열의 현재 원소에 해당하는 수가 나올 때까지 스택을 쌓는다
{
stack[++stack_idx] = ++push_count;
push_pop[push_pop_idx++] = 1;
}
else if (stack[stack_idx] == arr[idx]) // 배열의 현재 원소에 해당하는 수는 스택에서 빼 입력한다.
{
stack[stack_idx--] = 0;
idx++;
push_pop[push_pop_idx++] = -1;
}
else // 스택에 쌓인 수가 현재 배열의 원소보다 크다면 원하는 배열을 만들 수 없다.
{
printf("NO\n");
return (0);
}
}
idx = -1;
while(++idx < push_pop_idx)
{
if (push_pop[idx] == 1)
printf("+\n");
else
printf("-\n");
}
// 도중에 배열을 완성할 수 없다는게 밝혀질 수 있으므로, push(+)와 pop(-)을 수행할때마다 따로 배열에 저장해두었다가 최종적으로 배열이 완성될경우 출력한다.
free(arr);
free(stack);
return (0);
}