백준_12789_도키도키간식드리미

 

 

 

 

 

 

문제 설명에는 스택을 활용하는 문제라고 적혀있지만, 큐와 스택을 동시에 활용하면 더 좋을 것 같아서

큐와 스택을 같이 활용하였습니다.

 

 

 

 

 

이 과정을 보시면, 왜 스택과 큐를 사용하는지 알 수 있습니다.

 

현재 줄 서있는 곳에서는, 먼저 줄 선 사람만 먼저 나갈 수 있습니다. ( 큐의 성질과 동일하죠.)

 

한 명씩만 설 수 있는 공간에서는, 나중에 들어온 사람만 먼저 나갈 수 있습니다. ( 스택의 성질과 동일합니다.)

 

 

 

문제 풀이)

이 문제를 풀기 위해서는 다양한 예시를 살펴봐야 합니다.

 

문제에 나온 예시와 위 사진을 보면, 결과가 나올 때 가지는 공통점이 있습니다.

 

바로 현재 줄 서있는 곳에 사람이 없다는 점입니다.

 

그렇다면, 현재 줄 서있는 곳(큐) 가 빌 때까지 반복문을 돌리면 될 것 같습니다.

 

또 하나 신경써야 할 점은, 

예를 들어 1번이 간식을 받고 나서 바로 뒤에 있는 번호가 2번 즉, 이어지는 번호가 아니라면 다른 줄로 이동해야 한다는 점입니다.

 

이렇게 하지 않으면, 큐가 빌 때까지 임시 줄로 모든 사람이 가버릴 수 있기 때문에, 이 조건을 꼭 넣어줘야 합니다.

 

 

 

큐와 스택 선언 및 기능 만들기)

#define N 1001

int queue[N];                // 현재 줄 서있는 곳
int stack[N];                // 함 명씩만 설 수 있는 공간
int q_front = 0, q_rear = 0; // 큐의 앞과 뒤
int s_top = 0, s_bottom = 0; // 스택의 앞과 뒤

void push_queue(int k);
void push_stack();
int pop_queue();
int pop_stack();

void push_queue(int k)
{
    queue[q_rear] = k;
    q_rear++;
}

void push_stack()
{
    stack[s_top] = pop_queue();
    s_top++;
}

int pop_queue()
{
    int k;
    k = queue[q_front];
    queue[q_front] = 0;
    q_front++;

    return k;
}
int pop_stack()
{
    int k;
    k = stack[s_top - 1];
    stack[s_top - 1] = 0;
    s_top--;

    return k;
}

스택과 큐를 선언하고, 데이터를 넣고 빼는 기능을 수행하는 함수를 만들어주었습니다.

 

이제 이 함수들을 이용하여 반복문을 돌리면 되겠죠.

 

 

main함수)

int main(void)
{
    int n;
    scanf("%d", &n);

    int num;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &num);
        push_queue(num);
    }

    int x = 1;
    while (q_front != q_rear)
    {
        for (int i = q_front; i < q_rear; i++)
        {
            if (queue[q_front] == x)
            {
                snack = pop_queue();
                x++;

                if (queue[i + 1] == x)
                {
                    continue;
                }
                else
                {
                    break;
                }
            }
            else
            {
                push_stack();
            }
        }

        for (int i = s_top - 1; i >= s_bottom; i--)
        {
            if (stack[i] == x)
            {
                snack = pop_stack();
                x++;

                if (stack[i - 1] == x)
                {
                    continue;
                }
                else
                {
                    break;
                }
            }
            else
            {
                break;
            }
        }
    }

    if (snack == n)
    {
        printf("Nice\n");
    }
    else
    {
        printf("Sad\n");
    }

    return 0;
}

 

이렇게 큐가 빌 때까지 while 문을 반복해주면 간식을 받았는지 안받았는지 확인할 수 있습니다.

 

간식을 받을 때마다 snack 변수에 번호를 저장하고, 반복문이 끝났을 때 마지막으로 간식을 받은 사람을 확인하여

 

Sad 혹은 Nice를 출력합니다.

 

 

 

전체 코드)

#include <stdio.h>
#define N 1001

int queue[N];                // 현재 줄 서있는 곳
int stack[N];                // 함 명씩만 설 수 있는 공간
int q_front = 0, q_rear = 0; // 큐의 앞과 뒤
int s_top = 0, s_bottom = 0; // 스택의 앞과 뒤
int snack;                   // 마지막으로 간식을 받은 사람의 번호

void push_queue(int k);
void push_stack();
int pop_queue();
int pop_stack();

int main(void)
{
    int n;
    scanf("%d", &n);

    int num;
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &num);
        push_queue(num);
    }

    int x = 1;
    while (q_front != q_rear)
    {
        for (int i = q_front; i < q_rear; i++)
        {
            if (queue[q_front] == x)
            {
                snack = pop_queue();
                x++;

                if (queue[i + 1] == x)
                {
                    continue;
                }
                else
                {
                    break;
                }
            }
            else
            {
                push_stack();
            }
        }

        for (int i = s_top - 1; i >= s_bottom; i--)
        {
            if (stack[i] == x)
            {
                snack = pop_stack();
                x++;

                if (stack[i - 1] == x)
                {
                    continue;
                }
                else
                {
                    break;
                }
            }
            else
            {
                break;
            }
        }
    }

    if (snack == n)
    {
        printf("Nice\n");
    }
    else
    {
        printf("Sad\n");
    }

    return 0;
}

void push_queue(int k)
{
    queue[q_rear] = k;
    q_rear++;
}

void push_stack()
{
    stack[s_top] = pop_queue();
    s_top++;
}

int pop_queue()
{
    int k;
    k = queue[q_front];
    queue[q_front] = 0;
    q_front++;

    return k;
}
int pop_stack()
{
    int k;
    k = stack[s_top - 1];
    stack[s_top - 1] = 0;
    s_top--;

    return k;
}