Day13_[BOJ 1874] 스택 수열/ C

Prologue

우리나라의 문해율(글을 읽을 수 있는 사람의 정도)는 99%입니다. 국민 100명 중 1명만이 글을 읽을 수 없다는 뜻입니다.
그런데, 우리나라 사람들이 읽지 못하는 단어 3가지가 있습니다.

1. 미시오
2. 당기시오
3. 적재금지

그런 의미에서 오늘은 stack에 대해서 적어보겠습니다.

Problem

그럼 문제를 살펴보겠습니다.
stack은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념입니다. 스택은 자료를 넣는 PUSH와 자료를 뽑는

"POP"

입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 LIFO 특성을 갖고있습니다.
이 문제에서는 1부터 n까지 수를 스택에 넣었다가 뽑아 늘어놓음으로써 하나의 수열을 만들고, 임의의 수열을 주었을 때, 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop연산을 수행해야 하는지를 알아내는 프로그램을 작성하는것이 목표입니다.

Problem Solving Methods

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

#define size 100002

int main() {
    int getnum;
    int getlist[size] = {0, };
    char stack[size * 2] = {0, };
    int stack_num[size] = {0, };
    
    scanf("%d", &getnum);
    for(int i = 1; i <= getnum; i++) {
        scanf("%d", &getlist[i]);
    }

    int count = 1, listcount = 1, upcount = 1, stack_top = 0;
    while(count <= getnum || stack_top > 0) {
        if(stack_top > 0 && stack_num[stack_top] == getlist[listcount]) {
            stack[upcount++] = '-';
            stack_top--;
            listcount++;
        } else if(count <= getnum) {
            stack[upcount++] = '+';
            stack_num[++stack_top] = count++;
        } else {
            printf("NO\n");
            return 0;
        }
    }

    for(int j = 1; j < upcount; j++) {
        printf("%c\n", stack[j]);
    }
    
    return 0;
}

우선, size만큼의 배열을 getlist, stack, stack_num 이렇게 3개를 선언합니다. 맨 첫줄에는 앞으로 몇개의 수를 줄 것 인지를 정수형태로 주고, 그 다음부터 한 줄씩 수를 입력합니다.

입력을 받은 수는 for문을 돌면서 getlist 배열에 들어갑니다.

만약 stack_top이 0보다 크고, stack_num과 getlist가 같다면 '-'를 출력하고, stack_top은 하나 줄이고, listcount는 하나 늘립니다.
만약 getnum이 count보다 크다면 '+'를 출력하고, 1 증가한 stack_num에 count를 더해줍니다.
만약, 둘 다 해당이 되지 않는다면, 수열이 이루어질 수 없기 때문에, NO를 출력합니다.

마지막으로 upcount를 돌며 앞서 저장해두었던 +와 -를 출력합니다.

Retrospect

오늘은 stack에 대해서 적어보았습니다.

Spec을 쌓기 위해 개발 공부하며 Stack을 쌓고있는 여러분, 가끔은 맛있는 Snack과 Steak를 먹으며 휴식하는 시간을 가지시길 바라며 오늘 글 마무리 하겠습니다.

감사합니다.