[백준] 24511번: queuestack 파이썬 풀이

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

이게 뭔소리지

 

큐스택 이 문제는 일단 문제를 이해하는 것 자체가 문제였다.

고맙게도 다른 분이 쉽게 그림과 함께 설명해놓은 블로그 글을 보고 이해했다...

 

문제 설명

도현이가 제안한 queuestack은 큐와 스택을 혼합한 자료구조입니다. queuestack은 N개의 자료구조(큐 혹은 스택)가 나열되어 있으며, 각 자료구조에 한 개의 원소가 들어 있다.

이 자료구조의 작동 방식은 간단하다. 새로운 원소를 첫 번째 자료구조에 삽입한 후, 이 자료구조에서 pop하여 나온 값을 두 번째 자료구조에 삽입하는 방식으로 마지막 자료구조까지 연속적으로 이어진다. 마지막 자료구조에서 나온 값을 리턴한다.

수열 C의 원소를 queuestack에 넣은 후, 리턴된 값을 출력하는 것이 목표다.

 

첫 번째 시도 - 시간 초과

처음에는 이중 for문으로 모든 자료구조를 차례대로 순회하며 값을 처리하는 방식으로 코드를 작성했다. 하지만 이 방법은 시간 복잡도가 너무 높아, N과 M의 범위가 클 때 시간 초과가 발생했다.

 

import sys
from collections import deque

n = int(sys.stdin.readline())
arr_a = list(map(int, sys.stdin.readline().split()))  # 큐와 스택을 구분하는 배열
arr_b = list(map(int, sys.stdin.readline().split()))  # 각 자료구조에 들어있는 원소
m = int(sys.stdin.readline())
arr_c = list(map(int, sys.stdin.readline().split()))  # 삽입할 원소들

for i in range(m):
    x = arr_c[i]
    for j in range(n):
        if arr_a[j] == 0:  # 큐인 경우
            temp = arr_b[j]
            arr_b[j] = x
            x = temp
    print(x, end=' ')

문제점
- 시간 복잡도: N개의 자료구조를 M번 반복하며 확인하기 때문에, 최악의 경우 O(N * M)의 시간 복잡도를 가진다. 이 경우 N과 M이 최대 100,000일 때, 100억 번의 연산이 필요하므로 시간 초과가 발생했다.

 

두 번째 시도 - 정답

 

스택의 경우 추가된 값 그대로 pop되기 때문에 스택은 없는 셈 치고  큐 자료구조의 특징을 활용했다. 큐의 특징을 이용해서 한번에 삽입할 값을 처리했다.

import sys
from collections import deque

n = int(sys.stdin.readline())
arr_a = list(map(int, sys.stdin.readline().split()))  # 큐(0) 또는 스택(1)을 구분하는 배열
arr_b = list(map(int, sys.stdin.readline().split()))  # 각 자료구조의 초기값
m = int(sys.stdin.readline())
arr_c = list(map(int, sys.stdin.readline().split()))  # 삽입할 수열

# 큐인 자료구조들의 값을 deque에 넣음
arr = deque()
for i in range(n):
    if arr_a[i] == 0:  # 큐인 경우
        arr.append(arr_b[i])

# 삽입할 원소들을 순차적으로 처리
for i in range(m):
    arr.appendleft(arr_c[i])

# 결과 출력
for i in range(m):
    print(arr.pop(), end=' ')

코드 설명
1. 큐인 자료구조들만 deque에 미리 넣는다. 
2. 삽입할 값들은 `appendleft`로 deque의 앞부분에 추가한다.
3. pop을 통해 결과를 차례대로 출력한다.