[BOJ] 백준 24511번: queuestack (C++)

 

- 문제 출처 : https://www.acmicpc.net/problem/24511

---

1. 생각

이번 문제는 queuestack 이라는 이름의 문제이다.

 

어떤 값을 입력받으면 이 값이 queue 또는 stack으로 이뤄진 자료구조들에 push되었다가,

각각의 자료구조의 pop 방식에 따라 다시 다음 자료구조로 넘어가서, 마지막에 pop된 값이 출력되는 문제였다.

 

queue와 stack을 모두 활용할 수 있는 구조인 deque를 사용해야겠다고 바로 생각이 들었고,

굉장히 단순하게 여러 deque를 만들어서 0, 1 에 따라 queue 처럼 쓸지 stack 처럼 쓸지 결정하면 되는구나 했지만,

이는 큰 착각이었다..

 

2. 난관 & 해결 방법

1) deque를 여러개 만들고 주어진 수가 모든 deque을 거치며 return 하는 방식

int N, M, value;
std::cin >> N;
std::deque <int> dq[N];
int* q_or_st = new int[N];
for (int i = 0; i < N; i ++)
    std::cin >> q_or_st[i];
for (int i = 0; i < N; i ++)
{
    std::cin >> value;
    dq[i].push_back(value);
}
std::cin >> M;
for (int i = 0; i < M; i ++)
{
    std::cin >> value;
    for (int j = 0; j < N; j ++)
    {
        dq[j].push_back(value);
        if (q_or_st[j]) //stack
        {
            value = dq[j].back();
            dq[j].pop_back();
        }
        else // queue
        {
            value = dq[j].front();
            dq[j].pop_front();
        }
    }
    std::cout << value << " ";
}

 

위 생각처럼, 문제에서 주어진대로 각각의 자료구조를 주어진 수가 다 push-pop을 하도록 만들었다.

stack 일때는 LIFO 방식이므로, back에 push된 자료가 바로 pop된다.

queue 일때는 FIFO 방식이므로, back에 push 되고, front 가 pop이 된다.

 

N개의 자료구조를 M개의 주어진 수가 모두 push-pop하게 되므로,

M * N 번의 수행을 하게 된다.

여기서 살짝 시간이 초과되지 않을까라는 걱정을 하게 되었는데, 역시나였다.

 

줄일 방법이 필요했다.

 

2)  stack일 때는 들어온 자료가 그대로 pop이 되는 점 활용

 

다시 시뮬레이션 해보니, stack은 들어온 수가 그대로 다음 자료구조로 넘어간다.

따라서 어떤 동작도 할 필요가 없다는 것을 알게 되어, 위 코드에서 stack 부분을 아예 빼버려도 동작이 같았다.

하지만 여전히 시간 초과는 극복할 수 없었다.

 

3) stack이라고 판별된 위치의 자료는 return 값에 영향을 아예 주지 않는다 -> 아예 담을 필요도 없음.

 

예시)

1 2 3 4 라는 자료에 7 8 9 가 들어온다. / 자료구조는 0 1 1 0 (queue, stack, stack,  queue) 이다.

그럼, 결과를 과정에 따라 살펴보게 되면,

1 2 3 4 -> 7 2 3 1 ( 4 return ) -> 8 2 3 7 (1 return ) -> 9 2 3 8 ( 7 return ) 이 된다.

 

여기서 발견한 것은 2, 3 이 이 모든 수행 과정에 영향을 끼치지 않는다는 것이다.

1 4 -> 7 1 ( 4 return ) -> 8 7 (1 return ) -> 9 8 ( 7 return ) 이 되어도 수행이 같다는 것이다.

그럼 애초에 stack으로 판별된 자료는 담을 필요 자체가 없어진 것이다.

 

4) 하나의 deque (또는 queue) 만 있으면 결과 도출 가능

 

1 4 -> 7 1 ( 4 return ) -> 8 7 (1 return ) -> 9 8 ( 7 return )

이 결과만 보면, 상당히 간단하게 queue의 push-pop을 반복한 구조처럼 보인다.

push(7) -> pop() -> push(8) -> pop() -> push(9) -> pop() 만으로도 만들어지는 모습이다.

그럼 굳이 각각의 자료구조를 가질 필요도 없이, 하나의 deque(또는 queue) 만으로 이 동작을 모두 구현할 수 있는 것이다.

 

std::cin >> N;
std::deque <int> dq;
int* q_or_st = new int[N];
for (int i = 0; i < N; i ++)
    std::cin >> q_or_st[i];
for (int i = 0; i < N; i ++)
{
    std::cin >> value;
    if (q_or_st[i] == 0)
        dq.push_back(value);
}
std::cin >> M;
for (int i = 0; i < M; i ++)
{
    std::cin >> value;
    dq.push_front(value);
    std::cout << dq.back() << " ";
    dq.pop_back();
}

 

위에서의 아이디어들을 토대로 수정한 코드이다.

deque 하나만 만들었고, q_or_st 를 통해 queue로 들어온 자료만 push 해줬다.

그리고 입력되는 자료들은 push_front -> pop_back 이 되며, 일반 queue처럼 동작하며 값을 return 해준다.

 

이러면, N + M 의 시간밖에 들지 않는 굉장히 간결한 방식이 되어 문제를 해결할 수 있게 되었다.

 

3. 코드 및 결론

[ 전체 코드 ]

#include <iostream>
#include <deque>

int main(void){
    int N, M, value;
    std::cin.tie(NULL);
    std::ios::sync_with_stdio(false);
    std::cin >> N;
    std::deque <int> dq;
    int* q_or_st = new int[N];
    for (int i = 0; i < N; i ++)
        std::cin >> q_or_st[i];
    for (int i = 0; i < N; i ++)
    {
        std::cin >> value;
        if (q_or_st[i] == 0)
            dq.push_back(value);
    }
    std::cin >> M;
    for (int i = 0; i < M; i ++)
    {
        std::cin >> value;
        dq.push_front(value);
        std::cout << dq.back() << " ";
        dq.pop_back();
    }
}

 

[ 결론 ]

 

만들고 보니 정말 간단한 문제였지만, 처음에 너무 문제를 곧이곧대로 받아들여서

deque의 배열을 만들어버리면서 돌고 돌아 정답에 도달하는데 꽤 오래걸렸다.

 

다음부터는 이런 구현문제를 풀때는 테스트 케이스들에 대해서 좀 더 고민해보면서

가장 효율적인 방식이 어떤 건지 고민해보는 과정을 거쳐봐야할 것 같다.