[6주차] 백준 1874번: 스택 수열_C언어

백준 1874: 스택 수열

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

1874번: 스택 수열

---

- 수열을 이루는 수의 개수 n을 입력받는다.

- 그 다음 줄 부터 차례대로 1이상 n 이하의 정수가 주어진다. (중복되는 수는 없음)

- 입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다.

//push= +, pop = -

- 만들 수 있다면 push와 pop을 표현하고 안된다면 "NO"라고 표시한다.

---

솔직히 문제를 읽고 너무 이해가 안돼서 계속 읽었다.

스택 수열에 대한 이해가 부족해서 처음에 문제를 잘 이해하지 못했던 것 같다.

구글링을 해보고나서야 제대로 문제가 이해가 되었다!-.,-

---

[참고] https://wtg-study.tistory.com/53

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

->스택의 상단 부분 수가 목표수보다 낮은 경우(push)

-> 스택의 상단 부분 수와 목표수가 같은 경우(pop)

-> 스택의 상단 부분 수가 목표수보다 높은 경우(NO)

---

#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) {
        if (top == -1 || stack[top] < arr[idx]) {
            stack[++top] = num++;
            result[result_idx++] = '+';
        }

        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;
}

[출처] https://wtg-study.tistory.com/53