[Baekjoon]백준 24511 queuestack(실버 3) - Python

문제설명

예제

다른 문제들에 비해 문제가 길고 복잡하다 문제를 이해하는데 꽤나 오랜 시간이 소요되었다 

간단하게 설명을 하자면 두번째 줄에는 queuestack의 상태가 저장이 되는데 0이라면 큐, 1이라면 스택이다

세번째 줄에는 그 queuestack에 들어있는 원소가 저장이 되고 마지막 줄에는 삽입될 원소들이 입력된다

큐는 FIFO 구조이기 때문에 pop이 발생하면 이전에 존재하던 원소가 제일 먼저 사라지지만 

스택은 LIFO 구조이기 때문에 pop이 발생하면 마지막에 들어온 원소가 제일 먼저 사라진다

그렇다면 이 문제에서는 0인 경우에는 원소의 교환이 이루어질거고, 스택이라면 그대로 유지될 것이다 

처음 코드에서는 이를 활용하여 0인 경우에 원소끼리 교환을 해주었고, 

인덱스가 마지막에 도착하면 그 값을 출력하도록 작성하였다

import sys

n = int(input())
queuestack = list(map(int, sys.stdin.readline().split()))
qs_element = list(map(int, sys.stdin.readline().split()))
m = int(input())
insert_element = list(map(int, sys.stdin.readline().split()))

for t in range(m):
    for i in range(n):
        if queuestack[i] == 0:
            qs_element[i], insert_element[t] = insert_element[t], qs_element[i]
        if i == n - 1:
            print(insert_element[t], end = ' ')

하지만 정답률 33퍼센트의 문제답게 시간초과가 발생하였다

이러한 방식으로 작성을 하면 두 개의 for문이 존재하기에 O(mn)의 시간 복잡도가 발생한다

그래서 메모장을 키고 다시 자세히 살펴보니 큐가 하나의 큐처럼 작동하는 것을 확인할 수 있다 

예제를 살펴보면 큐는 1 4 만 해당하는데 시간이 지날수록 큐의 맨 앞의 수는 큐의 뒤로 이동하고

맨 뒤의 수는 리턴값으로 출력된다

이를 참고하여 하나의 덱을 만들어주고 그 덱에 해당 값들을 넣어 코드를 작성하면 된다

import sys
from collections import deque

n = int(input())
queuestack = list(map(int, sys.stdin.readline().split()))
qs_element = list(map(int, sys.stdin.readline().split()))
m = int(input())
insert_element = list(map(int, sys.stdin.readline().split()))

flag = deque()

for i in range(n):
    if queuestack[i] == 0:
        flag.appendleft(qs_element[i])
        
for i in insert_element:
    flag.append(i)
    print(flag.popleft(), end = ' ')

간단하게 코드에 대해 말하자면 결국 삽입하는 원소 또한 큐의 제일 왼쪽에 삽입되는걸로 이해할 수 있다

처음에 입력받은 큐의 제일 오른쪽 즉 마지막에 위치한 원소부터 m개의 값이 리턴되므로

flag라는 덱을 하나 만들어 원소들 중에 큐에 해당하는 원소를 추가하고, 

삽입할 원소는 삽입되는 순서대로 리턴되므로 마지막 세줄에 해당하는 for문에 의해 실행된다고 할 수 있다