#24511 queue & stack

⭐ 문제

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

queuestack의 작동은 다음과 같다.

 $x_0$을 입력받는다.
$x_0$을
$1$번 자료구조에 삽입한 뒤
$1$번 자료구조에서 원소를 pop한다.
그때 pop된 원소를 $x_1$이라 한다.

$x_1$을
$2$번 자료구조에 삽입한 뒤
$2$번 자료구조에서 원소를 pop한다.
그때 pop된 원소를 $x_2$이라 한다.
...

$x_{N-1}$을
$N$번 자료구조에 삽입한 뒤
$N$번 자료구조에서 원소를 pop한다. 그때 pop된 원소를
$x_N$이라 한다.

$x_N$을 리턴한다.

$M$의 수열 $C$를 가져와서 수열의 원소를 앞에서부터 차례대로 queuestack에 삽입할 것이다. 이전에 삽입한 결과는 남아 있다.

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

---

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

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

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

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

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

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

---

📝 예제

입력
4
0 1 1 0
1 2 3 4
3
2 4 7

출력
4 1 2

---

풀이

도대체 무슨 소리인지 모르겠다.
이게 뭔 소리람.╱(・-・ꐦ)👂╲
일단 문제부터 이해해보자면 이렇다는 것이다.

N = 4
A = [0, 1, 1, 0]   # 0=큐, 1=스택
B = [1, 2, 3, 4]   # 각 칸의 초기 값
M = 3
C = [2, 4, 7]      # 순서대로 넣을 것들 

일단 C가 2일 때부터 보자

A = [0, 1, 1, 0]   # 0=큐, 1=스택
B = [1, 2, 3, 4] 

[1] 인 상태에다가 C가 2라고 했으니 2를 넣으면 [1,2]
queue는 FIFO 이므로 1이 pop되고 [2]가 남는다.

[2] 인 상태에다가 그 전 pop된 값이 1이므로 넣으면 [2,1]
stack은 LIFO 이므로 1이 pop되고 [2]가 남는다.

[3] 인 상태에다가 그 전 pop된 값이 1이므로 넣으면 [3,1]
stack은 LIFO 이므로 1이 pop되고 [3]이 남는다.

[4] 인 상태에다가 그 전 pop된 값이 1이므로 넣으면 [4,1]
queue는 FIFO 이므로 4가 pop되고 [1]이 남는다.

--> C가 2일 때 결과는 4

문제가 이해가 됐으면 그 다음에는 코딩을 해보자.

✅ stack(1) 은 “그냥 통과” → 무시해도 됨
✅ queue(0) 만 “기존에 있던 값”을 실제로 내보냄

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

N = int(input())
A = list(map(int, input().split())) # 0 = queue, 1 = stack
B = list(map(int, input().split())) # 초기 상태
M = int(input())
C = list(map(int, input().split())) # 넣을 값들


pipe = deque(b for a, b in zip(A, B) if a == 0)

ans = []
for c in C:
    if pipe:
        # 오른쪽(마지막 큐)의 값이 리턴
        ans.append(pipe.pop())
        # 새 입력값은 왼쪽(첫 큐)으로 들어가 저장
        pipe.appendleft(c)
    else:
        # 큐가 하나도 없으면 스택만 있으므로 입력값이 그대로 리턴
        ans.append(c)

print(*ans)

zip(A,B)

A = [0, 1, 1, 0]
B = [1, 2, 3, 4]
for a, b in zip(A, B):
   print(a, b)

0 1
1 2
1 3
0 4