[Silver III] queuestack - 24511

문제 링크

성능 요약

메모리: 48268 KB, 시간: 212 ms

분류

자료 구조, 덱, 큐, 스택

제출 일자

2023년 12월 26일 11:44:08

문제 설명

한가롭게 방학에 놀고 있던 도현이는 갑자기 재밌는 자료구조를 생각해냈다. 그 자료구조의 이름은 queuestack이다.

queuestack의 구조는 다음과 같다. 1$1$번, 2$2$번, ... , N$N$번의 자료구조(queue 혹은 stack)가 나열되어있으며, 각각의 자료구조에는 한 개의 원소가 들어있다.

queuestack의 작동은 다음과 같다.

x0$x_0$을 입력받는다.
x0$x_0$을 1$1$번 자료구조에 삽입한 뒤 1$1$번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 x1$x_1$이라 한다.
x1$x_1$을 2$2$번 자료구조에 삽입한 뒤 2$2$번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 x2$x_2$이라 한다.
...
xN−1$x_{N-1}$을 N$N$번 자료구조에 삽입한 뒤 N$N$번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 xN$x_N$이라 한다.
xN$x_N$을 리턴한다.

도현이는 길이 M$M$의 수열 C$C$를 가져와서 수열의 원소를 앞에서부터 차례대로 queuestack에 삽입할 것이다. 이전에 삽입한 결과는 남아 있다. (예제 1$1$ 참고)

queuestack에 넣을 원소들이 주어졌을 때, 해당 원소를 넣은 리턴값을 출력하는 프로그램을 작성해보자.

입력

첫째 줄에 queuestack을 구성하는 자료구조의 개수 N$N$이 주어진다. (1≤N≤100000$1 \leq N \leq 100\,000$)

둘째 줄에 길이 N$N$의 수열 A$A$가 주어진다. i$i$번 자료구조가 큐라면 Ai=0$A_i = 0$, 스택이라면 Ai=1$A_i = 1$이다.

셋째 줄에 길이 N$N$의 수열 B$B$가 주어진다. Bi$B_i$는 i$i$번 자료구조에 들어 있는 원소이다. (1≤Bi≤1000000000$1 \leq B_i \leq 1\,000\,000\,000$)

넷째 줄에 삽입할 수열의 길이 M$M$이 주어진다. (1≤M≤100000$1 \leq M \leq 100\,000$)

다섯째 줄에 queuestack에 삽입할 원소를 담고 있는 길이 M$M$의 수열 C$C$가 주어진다. (1≤Ci≤1000000000$1 \leq C_i \leq 1\,000\,000\,000$)

입력으로 주어지는 모든 수는 정수이다.

출력

수열 C$C$의 원소를 차례대로 queuestack에 삽입했을 때의 리턴값을 공백으로 구분하여 출력한다.

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
m = int(input())
c = list(map(int, input().split()))
queue = deque()
for i in range(n):
    if a[i] == 0:
        queue.append(b[i])
for i in c:
    queue.appendleft(i)
    print(queue.pop(), end=" ")

풀이

문제가 잘 이해되지 않아 문제 이해를 위해서 구글을 검색해봤다. a의 요소가 0이면 큐, 1이면 스택이며 b의 해당 위치에 a에서의 큐를 뽑아주면 될 것 같았다.

a에서 큐인 인덱스들을 b 리스트에서 해당 인덱스 요소들을 뽑아 큐 리스트에 넣어줬다.

이후에 설명되어 있던 방식으로 왼쪽에는 c 요소를 오른쪽에는 요소를 빼서 출력시켜줬다.

모두 스택인 경우에는 c 리트스의 요소를 계속 왼쪽으로 넣는 방식으로 똑같이 하면 스택 출력과 같은 형식을 뽑아낼 수 있다.