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

백준 1874 : 스택 수열

 

문제 링크

www.acmicpc.net/problem/1874

1874번: 스택 수열

 

 

문제 내용

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다.

임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop연산을 수행해야 하는지를 알아내자.

이를 계산하는 프로그램을 작성하라.

• push : +
• pop : -

n=8일 때, 

input : 4 3 6 8 7 5 2 1

output : + + + + - - + + - + + - - - - -

 

 

Idea

이 문제는 솔직히 푸는 것보다 읽고 이해하는데 더 오래 걸렸다...;;

정리하자면,

1. n을 입력받는다.
2. 1부터 n까지의 수를 조합하여 목표하는 수열을 입력한다.(단, 중복은 없다)
3. 1부터 n까지 오름차순으로 push 혹은 pop을 할 수 있는 스택이 존재한다.
4. 이 스택으로 목표하는 수열을 만들 수 있는지 검사한다.
5. 만들 수 있다면 push와 pop을 표현하고 안된다면 "NO"라고 표시한다.

 

LIFO 방식에 오름차순인 스택은 3가지 규칙을 이용해 문제를 풀이할 수 있다.

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

 

 

Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 100000
 
char result[SIZE * 2];
int stack[SIZE];
int top = -1;
 
int main() {
    int n;
    scanf("%d", &n);
 
    //목표 수열 입력
    int* arr = (int*)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
 
    int num = 1;
    int idx = 0, result_idx = 0;
    while (1) {
        //스택에 있는 수가 목표 수 보다 낮은 경우
        //push(+)
        if (top == -1 || stack[top] < arr[idx]) {
            stack[++top] = num++;
            result[result_idx++] = '+';
        }
        //스택 상단부분의 수가 목표 수와 같은 경우
        //pop(-)
        else if (stack[top] == arr[idx]) {
            top--;
            result[result_idx++] = '-';
            idx++;
        }
        //스택의 상단부분의 수가 목표 수 보다 높은경우
        //원하는 수열을 만들 수 없음
        else {
            printf("NO\n");
            return 0;
        }
        if (result_idx == n * 2) break;
    }
    
    //결과 출력
    for (int i = 0; i < result_idx; i++)
        printf("%c\n", result[i]);
 
    return 0;
}