BOJ - [Array - 10845 큐] - Silver IV🥈

문제

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

설명

큐(Queue)?

이 문제도 저번문제 스택과 같이 자료구조의 형태중 하나인 큐를 소스로 표현하라는 문제가 되겠다.

큐(Queue)는 사진으로 표현하면 요-런? 느낌

Source : GIPHY

위 움짤 처럼 우리가 줄을 서는 것을 상상하면 된다.

줄은 뒤에서 사람이 유입되고 앞에서 부터 사람이 빠지게 되는데 자료구조의 형태인 큐 또한 마찬가지이다.

큐에서는 제일 나중에 들어온 자료가 먼저 나갈 수 없다. (스택 에서 가능하다)

Source : GIPHY

이렇게 먼저 들어온 자료가 먼저 나가는 이러한 특징을 보고 FIFO(First In First Out)이라 하며, 이러한 자료 형태는 이렇게 줄 서는 것 말고도 컴퓨터에서도 많이 접해볼 수 있었을텐데 대표적으로 프린터에서 무언가를 인쇄할때다.

Source : GIPHY

우리가 여러개의 문서를 인쇄 할때 여러문서를 모두 컴퓨터에서 열고 전부 인쇄버튼을 누르면 당연한 소리지만 대부분의 인쇄기는 한번에 한장의 문서밖에 인쇄 할 수 없기 때문에 먼저 요청이 들어온 문서의 인쇄를 시작함과 동시에 다른 문서는 대기열에 올리고 현재 인쇄 중인 문서가 모두 인쇄가 완료되면 대기열에 있는 문서중 제일 먼저 대기열에 올라온 문서부터 인쇄를 계속 진행하고 대기열에 문서가 모두 없어질때까지 계속 작업을 진행하게 된다.

※ 대기열은 Queue(큐)의 번역어 이기도 하다.

큐 자료구조에 대한 설명은 이정도로 하기로 하고 한번 문제를 살펴 보도록 하자.

문제 풀이

이문제는 전에 풀었던 스택에서 썼던 소스를 조금 고치는 것 만으로도 푸는 것이 가능하다. 게다가 Push, Size, Empty 함수는 그대로 재탕하는것도 가능하다!

Source : GIPHY

~~오—예-~~

이것은 스택과 큐에 자료를 삽입할때는 알고리즘이 동일하기 떄문에 그런 것이고, 반대로 자료를 빼내는 명령어인 Pop에 경우 큐 자료 구조를 위해서 별도로 다시 코딩을 해줘야 한다.

따라서 스택과 달리 큐에서 수정된 소스만 집중적으로 설명해 보도록 하겠다.

스택에 대한 설명은 여기 : https://hoshi2710.github.io/백준/10828.html

...
int size_cnt = 0;
void pop(void)
{
    if (size_cnt == 0)
        printf("-1\n");
    else
    {
        printf("%d\n", stack[size_cnt - 1]);
        stack[size_cnt - 1] = 0;
        size_cnt--;
    }
}
int main()
{
	...
}

Pop 명령에 경우 원래 스택에서는 나중에 들어온 자료를 먼저 뺴내야 했기 때문에 stack[0]의 자료를 빼내고 나머지 자료를 빈칸을 매우기 위해 당기는 작업이 필요했으나 큐는 먼저 들어온 자료가 먼저 나가는 구조 이므로 stack[size_cnt-1]의 자료를 빼주면 되며, 따로 스택에서 처럼 당기는 작업 없이 size_cnt의 값을 1 빼주는 작업만 해주면 된다.

(stack에서 쓴 소스를 그대로 수정한거 여서 배열 이름이 stack으로 되어 있다. 실제 문제도 stack이라는 배열 명으로 제출하였으나 이 밑에서 부터는 stack이 아닌 queue라고 배열 이름을 바꾼 상태로 설명을 이어 가보도록 하겠다.)

다음 Front, Back 함수를 구현해 줘야하는데 두 함수는 배열을 수정하는 함수가 아닌 그냥 출력하는 함수 이므로 아래와 같이만 구현해 주면 끝이다.

...
void front(void)
{
    if (size_cnt == 0)
        printf("-1\n");
    else
        printf("%d\n", queue[size_cnt-1]);
}
void back(void)
{
    if (size_cnt == 0)
        printf("-1\n");
    else
        printf("%d\n", queue[0]);
}
int main()
{
	...
}

stack에서 사용했던 Top 함수를 응용하면 쉽게 만들 수 있다.

그 이외에는 queue에서 사용하는 명령어를 해석 할 수 있도록 main함수에서 추가적으로 아래와 같이 적어주었다.

...
int main()
{
	...
else if (strcmp(command, "front") == 0)
     front();
else if (strcmp(command, "back") == 0)
     back();
	...
}

stack에서 이용했던 Top 명령어를 읽는 소스를 지우고 그 대신 Front, Back 명령어를 읽어 들일 수 있도록 소스를 위와 같이 수정해 주었다.

이렇게 Queue를 위한 소스가 완성되었으며 풀소스는 다음과 같다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
int queue[10000], size_cnt = 0;
void push_internal(void)
{
    for (int i = size_cnt; i > 0; i--)
        queue[i] = queue[i - 1];
}
void push(int input)
{
    if (size_cnt != 0)
        push_internal();
    queue[0] = input;
    size_cnt++;
}
void pop(void)
{
    if (size_cnt == 0)
        printf("-1\n");
    else
    {
        printf("%d\n", queue[size_cnt - 1]);
        queue[size_cnt - 1] = 0;
        size_cnt--;
    }
}
void size(void)
{
    printf("%d\n", size_cnt);
}
void empty(void)
{
    int tmp = size_cnt == 0 ? 1 : 0;
    printf("%d\n", tmp);
}

void front(void)
{
    if (size_cnt == 0)
        printf("-1\n");
    else
        printf("%d\n", queue[size_cnt-1]);
}
void back(void)
{
    if (size_cnt == 0)
        printf("-1\n");
    else
        printf("%d\n", queue[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, "front") == 0)
            front();
        else if (strcmp(command, "back") == 0)
            back();
    }

    return 0;
}

결과 링크 : http://boj.kr/d412c6a7753b456abdd4b932c2028cf9

문제

설명

큐(Queue)?

문제 풀이

Contents