백준_24511_queuestack

 

문제의 제목이 questack 이기 때문에 queue 와 stack 을 이용해 푸는 문제라고 착각하기 쉽습니다.

 

물론 그렇게 풀어도 되지만, 문제의 시간 제한이 1초이기 때문에, 최대한 시간이 적게 걸리는 방식으로 풀어야 합니다.

 

예제를 보며 작동 방식을 이해하면 어떤 식으로 풀어야 하는지 알 수 있습니다.

 

 

 

예제1번)

문제에서 친절하게 각 상태에 대한 큐스택 내부를 차례차례 알려주었습니다.

 

입력 2번째 줄에서 i번 자료구조가 큐인지 스택인지 알려준 후, b를 입력받습니다.

 

A배열

0	1	1	0
[0]	[1]	[2]	[3]

 

B배열

1	2	3	4
[0]	[1]	[2]	[3]
queue	stack	stack	queue

 

이런 식으로, A배열의 값에 따라 B배열에서 stack인지 queue인지 결정됩니다.

 

그 후, C 배열을 입력받아 하나씩 B에 넣고 pop 하고를 반복해 나오는 값을 출력하는 방식입니다.

 

 

C배열

2	4	7
[0]	[1]	[2]

 

 

****과정****

1. c배열에 첫 번째 값을 B배열의 첫 번째 인덱스에 넣습니다. (B배열을 다차원 배열이라 생각하면 편합니다.)

1 , 2	2	3	4
[0]	[1]	[2]	[3]

 

2. B배열의 첫번째 인덱스에서 pop 해서 다음 인덱스에 넣습니다. 이때, 스택인지 큐인지에 따라 나오는 값이 바뀌게 됩니다.

[0]인덱스는 큐 이기 때문에 먼저 들어가있던 1이 나오게됩니다. 

2	2 , 1	3	4
[0]	[1]	[2]	[3]

 

3. 2번과 동일한 과정을 합니다. [1]인덱스는 스택이기 때문에 나중에 들어온 1이 나옵니다.

2	2	3 , 1	4
[0]	[1]	[2]	[3]

 

4. [2]인덱스 또한 스택이기 때문에 나중에 들어온 1이 나옵니다.

2	2	3	4 , 1
[0]	[1]	[2]	[3]

 

5. [3]인덱스는 큐이기 때문에 먼저 들어가있던 4가 나오게 됩니다. 마지막으로 나온 4 출력.

남아있는 데이터 : {2,2,3,1}

 

1~5번 과정이 C 배열의 값을 하나 넣었을 때의 과정입니다.

이 과정을 C 배열 값 개수만큼 반복하면 됩니다.

 

문제의 예시를 보면, 이 과정을 한번 더 반복했을 때는 {4,2,3,2} , 그 다음 반복하면 {7,2,3,4} 가 남습니다.

 

근데, 이 과정을 반복하다보니 이상한 점이 있습니다.

 

바로 스택인 경우는 값이 바뀌지 않고 계속 고정되어있고, 출력되는 값에 영향을 미치지 않는다는 점입니다.

 

 

그렇다면, B배열을 처음부터 {1,4} ( 둘다 큐 ) 로 설정하고 위 과정을 반복해도 결과가 같을까요?

 

같습니다. 

 

 

 

그리고, 출력을 보면 4 1 2 가 출력되었습니다.

4와 1은 B배열의 큐에 들어있는 값이고, 2는 C배열의 첫 번째 값입니다.

 

그럼 저희는 위와 같이 복잡한 과정을 거치지 않고 그냥 큐에 들어있는 값과 C에 들어있는 값을 차례대로 출력하면 된다는 것을 알았죠. 이제 코드를 짜보겠습니다.

 

 

큐의 선언과 push , pop 함수)

#define N 200001	//들어올 수 있는 최대 데이터 개수 200000개

int queue[N];
int front = 0, rear = 0;
int push(int k, int queue[])
{
    queue[rear] = k;
    rear++;
    return 1;
}

int pop(int queue[])
{
    if (front == rear)
    {
        printf("underflow\n");
        return -1;
    }
    int k;
    k = queue[front];
    queue[front] = 0;
    front++;

    return k;
}

아직 큐에 대해 잘 모르신다면, 큐를 이용해 푼 문제를 먼저 보고 오시는 것을 추천드립니다.

https://sol248.tistory.com/17

백준_10845_큐(queue)

 

 

main함수)

#include <stdio.h>
#define N 200001
int queue[N];
int front = 0, rear = 0;
int push(int k)
{
    queue[rear] = k;
    rear++;
    return 1;
}

int pop()
{
    if (front == rear)
    {
        printf("underflow\n");
        return -1;
    }
    int k;
    k = queue[front];
    queue[front] = 0;
    front++;

    return k;
}

int main(void)
{
    int n = 0;                  //
    scanf("%d", &n);            //
    int a[n];                   //
    for (int i = 0; i < n; i++) // 큐인지 스택인지 파악하기 위한 a배열 생성후 입력받기
    {                           //
        scanf("%d", &a[i]);     //
    } //

    int b = 0;                  //
    for (int i = 0; i < n; i++) //
    {                           //
        scanf("%d", &b);        // 메모리와 시간을 아끼기 위해
        if (a[i] == 0)          // b를 배열이 아닌 int형 변수로 설정하고
        {                       // 스택이면 그냥 패스하고
            push(b);            // 큐면 그때그때 push해주는 방식
        } //
    } //

    int temp = 0, m = 0;                          //
    for (int m = front; m <= (rear - 1) / 2; m++) //
    {                                             //
        temp = queue[m];                          // 출력하는 순서를 맞추기 위해
        queue[m] = queue[rear - 1 - m];           // 큐의 순서 변경
        queue[rear - 1 - m] = temp;               //
    } //

    int k = 0;
    scanf("%d", &k);
    for (int i = 0; i < k; i++) // c 입력받고 push
    {
        int c = 0;
        scanf("%d", &c);
        push(c);
    }

    for (int i = 0; i < k; i++) // 큐에서 하나씩 뽑아서 출력
    {
        printf("%d ", pop());
    }
    printf("\n");
    return 0;
}

 

 

 

 

전체 코드)

#include <stdio.h>
#define N 200001
int queue[N];
int front = 0, rear = 0;
int push(int k)
{
    queue[rear] = k;
    rear++;
    return 1;
}

int pop()
{
    if (front == rear)
    {
        printf("underflow\n");
        return -1;
    }
    int k;
    k = queue[front];
    queue[front] = 0;
    front++;

    return k;
}

int main(void)
{
    int n = 0;                  //
    scanf("%d", &n);            //
    int a[n];                   //
    for (int i = 0; i < n; i++) // 큐인지 스택인지 파악하기 위한 a배열 생성후 입력받기
    {                           //
        scanf("%d", &a[i]);     //
    } //

    int b = 0;                  //
    for (int i = 0; i < n; i++) //
    {                           //
        scanf("%d", &b);        // 메모리와 시간을 아끼기 위해
        if (a[i] == 0)          // b를 배열이 아닌 int형 변수로 설정하고
        {                       // 스택이면 그냥 패스하고
            push(b);            // 큐면 그때그때 push해주는 방식
        } //
    } //

    int temp = 0, m = 0;                          //
    for (int m = front; m <= (rear - 1) / 2; m++) //
    {                                             //
        temp = queue[m];                          // 출력하는 순서를 맞추기 위해
        queue[m] = queue[rear - 1 - m];           // 큐의 순서 변경
        queue[rear - 1 - m] = temp;               //
    } //

    int k = 0;
    scanf("%d", &k);
    for (int i = 0; i < k; i++) // c 입력받고 push
    {
        int c = 0;
        scanf("%d", &c);
        push(c);
    }

    for (int i = 0; i < k; i++) // 큐에서 하나씩 뽑아서 출력
    {
        printf("%d ", pop());
    }
    printf("\n");
    return 0;
}