백준 24511번 Queuestack: C언어 풀이

백준 24511 Queuestack 문제의 C언어 해설입니다.
복잡한 자료구조 시뮬레이션을 시간 초과 없이 해결하기 위해 스택을 무시하고 큐의 요소만을 처리하여 단순화하는 방법을 설명합니다.

전략

컨베이어 벨트

문제에서 주어진 로직을 그대로 구현했더니 시간 초과가 났다.

복잡한 문제 지문을 단순화해서 생각해볼 필요가 있다.

먼저 스택 안에 들어있는 원소는 고려할 필요가 없다.
First in Last out, 스택을 나올 일이 없기 때문이다.

큐에 들어있는 원소는 계속해서 오른쪽 큐로 이동한다.
즉 처음 큐에 들어있는 원소는 계속해서 오른쪽 큐로 이동한다.
마치 컨베이어 벨트처럼.

즉 굳이 작동시켜보지 않아도 출력을 알 수 있다.
가장 오른쪽 숫자부터 차례로 리턴 될 것이다.

예시로 예제 입력 1을 보자

4
0 1 1 0
1 2 3 4
3
2 4 7

출력 순서는 다음과 같다.

먼저 최우측 큐에 들어있는 4가 출력된다.
그 다음 왼쪽 큐에 들어있는 1이 출력된다.
(스택에 들어있는 2, 3은 스택을 탈출할 수 없다. )

다음은 큐스택에 push해준 차례대로 2, 4, 7이 출력된다.
수열의 길이 M은 3이다. 따라서 앞에서 부터 잘라 4, 1, 2 까지가 정답이 된다.

따라서 그냥
큐에 들어있는 값을 역방향으로
삽입할 수열의 값을 정방향으로 출력해주기만 하면 된다.

코드

#include <stdio.h>

#define MAX_SIZE 100000
#define QUEUE 0

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

    int qs_types[MAX_SIZE];
    int qs_elements[MAX_SIZE];

    for (int i = 0; i < qs_size; i++)
    {
        scanf("%d", &qs_types[i]);
    }
    for (int i = 0; i < qs_size; i++)
    {
        scanf("%d", &qs_elements[i]);
    }

    int insert_count;
    scanf("%d", &insert_count);

    for (int i = qs_size - 1; insert_count != 0 && i >= 0; i--)
    {
        if (qs_types[i] == QUEUE)
        {
            printf("%d ", qs_elements[i]);
            insert_count--;
        }
    }

    for (; insert_count != 0; insert_count--)
    {
        int append_element;
        scanf("%d", &append_element);
        printf("%d ", append_element);
    }
}