BOJ - [Array - 10828 스택] - Silver IV 🥈

문제

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

설명

이 문제는 자료구조의 종류 중 스택에 대해서 알아보기에 좋은 문제 이며 개인적으로 이런 문제를 풀면서 스택의 원리를 이해하기에 좋다.

스택의 구조를 간단하게 요약하면 요런 느낌…?🤔

Source : GIPHY

스택은 위 움짤 처럼 자료를 쌓아 서 저장하는 것을 상상하면 된다.

쉽게 이해가 안된다면 햄버거에 들어가는 참깨 빵, 패티, 양상추, 치즈 등의 요소를 모두 자료라고 생각하면 이해하기 수월할 것이다.

~~빱빠빠라빠~~🍔

스택의 특징?

스택은 FILO의 특징을 가지고 있다.

FILO : First In Last Out 의 줄임 말로 첫 번째로 들어간 자료는 다시 빼낼 때 제일 마지막에 나온다는 의미를 지니고 있다.

우리가 완성된 햄버거에서 만약 피클을 빼고 싶다면 피클 위에 있는 빵과 그 이외의 요소들을 모두 들어 올려야 한다는 것을 상상하면 쉬울 것 이다.

따라서 어떤 스택에 1, 2, 3, 4, 5, 6, 7, 8, 9 가 차례대로 추가되면 다시 빼낼 때는 9, 8, 7, 6, 5, 4, 3, 2, 1

배경 지식은 이 정도면 충분할 것 같고 한번 문제를 살펴보도록 하자.

문제 풀이

이 문제는 스택을 구현해야 하고 이 문제에서 만들어질 수 있는 스택의 최대 크기는 대략 10000이므로 다음과 같이 정수 형 배열을 만들어 주도록 한다.

#include <stdio.h>

int stack[10000];
...

int main()
{
...
}

또 명령어를 받을 개수 또한 입력 받아야 하므로 다음과 같이 입력 문 과 계속해서 명령어를 반복 적으로 입력 받아야 하므로 이를 위한 반복문과 입력 문 또한 적어준다.

#include <stdio.h>

...

int main()
{
	int n,command[10];
	scanf("%d",&n);
	for (int i = 0; i < n; i++)
  {
     scanf("%s", command);
	}
	...
}

이 정도면 유저로 부터 받아야할 입력부분은 모두 완성이 되게된다. 그러나 여기서 지금까지 쳐온 소스와의 차이점이라면 명령어를 받아야 하기 때문에 command라는 문자열 변수를 만들고 문자열을 입력 받도록 하였다는 점이다.

그 다음에는 문제에서 말하는 다음 5개의 기능을 하나하나 구현해줘야 한다.

Push, Pop, Size, Empty, Top

나는 이 5가지 기능을 모두 함수로 구현해주었다.

#include <stdio.h>

...
int size_cnt=0;
void pull_internal(void) //스택 맨 윗부분의 빈공간을 매우기 위해 자료들을 앞으로 당기는 함수
{
    while (stack[0] == 0)
    {
        for (int i = 0; i < size_cnt; i++)
            stack[i] = stack[i + 1];
    }

}
void push_internal(void) //스택에 새로운 자료를 삽입하기 위해서 자료를 뒤로 미루는 함수
{
    for (int i = size_cnt; i > 0; i--)
        stack[i] = stack[i - 1];
}

void push(int input) //Push 기능
{
    if (size_cnt != 0)
        push_internal();
    stack[0] = input;
    size_cnt++;
}
void pop(void)  //Pop 기능
{
    if (size_cnt == 0)
        printf("-1\n");
    else
    {
        int tmp = stack[0];
        stack[0] = 0;
        if (size_cnt != 1)
            pull_internal();
        size_cnt--;
        printf("%d\n", tmp);
    }
}
void size(void)  //Size 기능
{
    printf("%d\n", size_cnt);
}
void empty(void)  //Empty 기능
{
    int tmp = size_cnt ==

함수 하나하나에 대한 자세한 설명은 나중에 기회가 된다면 이 게시글에 추가하든지 별도의 게시글로 작성해볼 수 있도록 하겠다.

~~절대 귀찮아서 그런게 아니다😑~~

위 기능을 모두 구현한 다음 이번에는 명령어를 받아 들이고 해석을 하는 부분을 만드는 것이다.

이부분은 if 문과 if else 문을 이용하면 어렵지 않게 만들 수 있을거라 생각했으나 문제는 다른언어와 달리 C언어는 내가 알던 방식으로 문자열을 비교할 수 없다는 것이었다…;;;

일반적으로 대부분의 언어에서 형식은 약간 다르지만 아래와 같은 꼴로 비교식을 쓰곤 하였다.

if(variable == "테스트")
{
	...
}

그러나 그냥 C언어에서는 이렇게 쓸 수 없음을 알게 되었고 구글링을 해보게 되었고 그결과 strcmp함수를 활용하면 된다는 점을 알게 되었다.

strcmp함수에 경우 string.h라는 헤더파일에 포함되어 있으며 이 문제에서 활용한 만큼만 간단하게 설명 해 보면 strcmp함수에 두개의 문자열 또는 문자열 변수가 들어가며, 두 문자열이 같을경우 0이 나오게 된다. 따라서 이를 이용해 명령어를 구별하는 소스를 포함하여 작성하면 다음과 같다.

...
int main() {
    int n, command_push;
    char command[10];
    scanf("%d", &n); //명령 갯수 입력
    for (int i = 0; i < n; i++)
    {
        scanf("%s", command);
        if (strcmp(command, "push") == 0)
        {
            scanf("%d", &command_push);
            push(command_push);
        }
        else if (strcmp(command, "pop") == 0)
            pop();
        else if (strcmp(command, "size") == 0)
            size();
        else if (strcmp(command, "empty") == 0)
            empty();
        else if (strcmp(command, "top") == 0)
            top();
    }

    return 0;
...

이렇게 모든 소스를 다 작성하게 되며 풀 소스는 다음과 같다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
int stack[10000], size_cnt = 0;
void pull_internal(void)
{
    while (stack[0] == 0)
    {
        for (int i = 0; i < size_cnt; i++)
            stack[i] = stack[i + 1];
    }

}
void push_internal(void)
{
    for (int i = size_cnt; i > 0; i--)
        stack[i] = stack[i - 1];
}

void push(int input)
{
    if (size_cnt != 0)
        push_internal();
    stack[0] = input;
    size_cnt++;
}
void pop(void)
{
    if (size_cnt == 0)
        printf("-1\n");
    else
    {
        int tmp = stack[0];
        stack[0] = 0;
        if (size_cnt != 1)
            pull_internal();
        size_cnt--;
        printf("%d\n", tmp);
    }
}
void size(void)
{
    printf("%d\n", size_cnt);
}
void empty(void)
{
    int tmp = size_cnt == 0 ? 1 : 0;
    printf("%d\n", tmp);
}
void top(void)
{
    if (size_cnt == 0)
        printf("-1\n");
    else
        printf("%d\n", stack[0]);
}
void show(void)
{
    for (int i = 0; i < size_cnt; i++)
        printf("%d\n", stack[i]);
}
int main() {
    int n, command_push;
    char command[10];
    scanf("%d", &n); //명령 갯수 입력
    for (int i = 0; i < n; i++)
    {
        scanf("%s", command);
        if (strcmp(command, "push") == 0)
        {
            scanf("%d", &command_push);
            push(command_push);
        }
        else if (strcmp(command, "pop") == 0)
            pop();
        else if (strcmp(command, "size") == 0)
            size();
        else if (strcmp(command, "empty") == 0)
            empty();
        else if (strcmp(command, "top") == 0)
            top();
    }

    return 0;
}

결과 링크 : http://boj.kr/5debdd88b54044519a6af6b90caf424a

문제

설명

스택의 특징?

문제 풀이

Contents