[백준] 24511번: queuestack - Python

https://www.acmicpc.net/problem/24511

 

오래간만에 재미있는 문제를 발견해서 블로그를 적습니다.

시간복잡도 + stack과 queue에 대해 생각해 볼 만한 문제입니다.

위에서 문제 설명을 보자면 queuestack 안에는 k개의 queue, n-k개의 stack이 들어있습니다.

그리고 그 자료구조에는 각각 원소가 하나씩 들어있고 원소를 넣었다 뺐다가 해서 마지막에 나오는 Xn을 구하라는 이야기인 것 같습니다.

문제 이해가 조금 어렵습니다.

예제를 가져와서 설명해드리겠습니다.

여기서 queuestack에 있는 자료구조는 queue stack stack queue입니다.

자료구조	큐	스택	스택	큐
원소	1	2	3	4

이제 2를 queuestack에 집어넣어 보겠습니다.

자료구조	큐	스택	스택	큐
원소	1, 2	2	3	4

자료구조	큐	스택	스택	큐
원소	2	2, 1	3	4

자료구조	큐	스택	스택	큐
원소	1	2	3, 1	4

자료구조	큐	스택	스택	큐
원소	1	2	3	4, 1

자료구조	큐	스택	스택	큐
원소	1	2	3	1

X4 = 4

이렇게 나옵니다. 그런데 잘 살펴보시면, 스택은 넣고 빼고 가 의미가 없는 것을 볼 수 있습니다.

import sys

n = int(sys.stdin.readline())
queue_stack = list(map(int,sys.stdin.readline().split()))
elements = list(map(int,sys.stdin.readline().split()))
m = int(sys.stdin.readline())
append_ele = list(map(int, sys.stdin.readline().split()))

for i in range(m):
    x0 = append_ele[i]
    for j in range(n):
        if queue_stack[j]: # 스택인 경우
            pass
        else: # 큐인 경우
            temp = elements[j]
            elements[j] = x0
            x0 = temp
    print(x0, end=" ")

그래서 코드를 이렇게 짜면, 깔끔하게 시간초과가 나옵니다. 

아이디어는 좋은데, 그러면 O(N*M)인 시간복잡도가 문제죠?

어떻게 시간복잡도를 줄일 수 있을까요?

---

한번 더 위의 예시를 살펴보겠습니다.

자료구조	큐	스택	스택	큐
원소	1	2	3	4

이제 2를 queuestack에 집어넣어 보겠습니다.

자료구조	큐	스택	스택	큐
원소	1, 2	2	3	4

자료구조	큐	스택	스택	큐
원소	2	2, 1	3	4

자료구조	큐	스택	스택	큐
원소	1	2	3, 1	4

자료구조	큐	스택	스택	큐
원소	1	2	3	4, 1

자료구조	큐	스택	스택	큐
원소	1	2	3	1

잘 보면 이상한 점이 보입니다.

큐에 있는 원소는 계속 바뀌지만, 스택에 있는 원소는 바뀌지 않습니다.

그러면, 스택이 없다고 생각하고 2를 queuestack에 넣어볼까요?

자료구조	큐	큐
원소	1, 2	4

자료구조	큐	큐
원소	2	4, 1

X4 = 4

완벽히 같은 값이 나옵니다.

그러면 코드로 구현할 때, 시간복잡도를 줄일 수 있을까요?

queuestack의 자료구조를 입력받고, stack일 때 원소를 버려버린다면?

queuestack의 원소정리에 O(N) 출력할 때 O(M)으로 O(N+M)이라는 시간복잡도가 나오게 됩니다.

import sys
from collections import deque

n = int(sys.stdin.readline())
queue_stack = list(map(int,sys.stdin.readline().split()))
elements = list(map(int,sys.stdin.readline().split()))

queue = deque()
for index, value in enumerate(queue_stack):
    if value == 0:
        queue.append(elements[index])

m = int(sys.stdin.readline())
append_ele = list(map(int, sys.stdin.readline().split()))

for i in range(m):
    x0 = append_ele[i]
    queue.appendleft(x0)
    print(queue.pop(), end=" ")

list 사용하셔도 됩니다.