[108]C++(Cpp) 백준 24511번: queuestack문제 (자료구조, 덱)

 

1. 첫 접근 (실패: 시간초과)

1) 배열 A와 이차원 배열 B를 만든다. (B의 행 부분은 순서, 열 부분의 0번 인덱스는 원래 요소, 1번 인덱스는 삽입된 요소를 넣는다.)

2) C의 수열을 하나씩 입력받아 queuestack에 삽입한다. 이때 배열 B를 이용해 queuestack 작동을 구현하였는데 이중 for문이 되어 시간복잡도가 증가한 것 같다.

이 방법으로는 이중 for문을 피할 수 없어 다른 접근 방법을 모색해야 했다.

#include <iostream>
using namespace std;

int main(void)
{
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    int N, M, element, poped;
    int* A; // 자료구조
    int** B; // queuestack에 들어있는 자료구조 이차원 배열
    int* C; //  queuestack에 삽입할 원소 배열
    cin >> N;
    A = new int[N];
    B = new int*[N];

    for (int i = 0; i < N; i++) // 이차원 배열 할당
    {
        B[i] = new int[2];
    }

    for (int i = 0; i < N; i++) // A
    {
        cin >> element;
        A[i] = element;
    }

    for (int i = 0; i < N; i++) // B
    {
        cin >> element;
        B[i][0] = element;
    }

    cin >> M;

    for (int i = 0; i < M; i++) // c
    {
        cin >> element;
        poped = element;
        for (int i = 0; i < N; i++) // queuestack에 삽입
        {

            B[i][1] = poped;
            if (A[i] == 0) // queue
            {
                poped = B[i][0];
                B[i][0] = B[i][1];
            }
            // stack일 때는 poped 바뀌지 않음
        }
        cout << poped << ' ';
    }

    return 0;
}

 

 

 

2. deque를 활용한 방법

 2-1 deque란?

deque란 double ended queue의 줄임말로 덱, 데크라고도 하는데 말그대로 양쪽에서 끝나는 큐이다.

 

stack은 최상단에서 삽입, 삭제가 동시에 일어나고 queue같은 경우는 한쪽에선 삽입, 다른 한쪽에선 삭제가 이루어진다.

 

deque같은 경우에는 양쪽 모두에서 삽입 삭제가 가능한데 stack과 queue를 합쳤다고 생각하면 된다.

 

 

deque 사용법.

https://blockdmask.tistory.com/73

[C++] deque container 정리 및 사용법

 2-2 풀이

고려해야 할 점

    1) queuestack 구조에서 stack 부분에는 항상 삽입된 값이 pop된다. (stack은 후입선출)

    2) queuestack 구조에서 queue 부분에는 항상 먼저 들어있던 값이 pop된다.(queue는 선입 선출)

 

==> 뒤 쪽에 있던 queue에 들어가있던 원소 부터 return된 후 삽입된 원소가 return된다.

 

ex) 수열 A가 0 1 1 0, 수열 B가 1 2 3 4, 수열 C가 2 4 7일 때를 가정해보자.

 

1.수열 C의 2를 queuestack에 삽입하면 각각의 자료구조에서 1(queue), 1(stack), 1(stack), 4(queue)를 pop한다,

(4 리턴) [2, 2, 3, 1]

2. 수열 C의 4를 queuestack에 삽입하면 각각의 자료구조에서 2(queue) , 2(stack) , 2(stack) , 1(queue) 을 pop한다.

(1 리턴) [4, 2, 3, 2]

3. 수열 C의 7를 queuestack에 삽입하면 각각의 자료구조에서 4(queue) , 4(stack) , 4(stack) , 2(queue) 을 pop한다.

(2 리턴) [7, 2, 3, 4]

 

뒤쪽의 queue부터 원래 들어있던 원소들이 queue 수만큼 먼저 리턴 된 후 삽입된 값이 리턴되므로 이 성질을 이용하여

dequeue에다가 queue의 반환값은 push_back() 해주고 stack의 반환값은 push_front()로 저장한다.

그 후로 dequeue를 pop_back()으로 반환값들을 공백을 주어 출력하면 된다.

#include <iostream>
#include <deque>
using namespace std;

int main(void)
{
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    deque<int> dq;
    int N, M, element;
    int* A; // 자료구조
    int* B; // queuestack에 들어있는 원소

    cin >> N;
    A = new int[N];
    B = new int[N];

    for (int i = 0; i < N; i++) // A
    {
        cin >> element;
        A[i] = element;
    }

    for (int i = 0; i < N; i++) // B
    {
        cin >> element;
        B[i] = element;
    }

    for (int i = 0; i < N; i++)
    {
        if (!A[i]) // queue일 때
        {
            dq.push_back(B[i]); //덱에다가 B[i] push_back
            // stack일때는 항상 삽입된 요소를 pop하므로 고려X
            // queue일때는 힝상 먼저 들어있던 요소를 pop함
        }
    }

    cin >> M;

    for (int i = 0; i < M; i++)
    {
        cin >> element; // 수열 C
        dq.push_front(element);
        cout << dq.back() << ' ';
        dq.pop_back();
    }

    return 0;
}