문제 설명

❓ 문제

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초 (추가 시간 없음)	1024 MB (추가 메모리 없음)	1389	515	431	36.869%

한가롭게 방학에 놀고 있던 도현이는 갑자기 재밌는 자료구조를 생각해냈다. 그 자료구조의 이름은 queuestack이다.
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에 삽입할 것이다. 이전에 삽입한 결과는 남아 있다. (예제 $1$ 참고)
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$)
  입력으로 주어지는 모든 수는 정수이다.
  
• 출력
  • 수열C 의 원소를 차례대로 queuestack에 삽입했을 때의 리턴값을 공백으로 구분하여 출력한다.
• 예시

  4
  0 1 1 0
  1 2 3 4
  3
  2 4 7
  
  # 출력
  4 1 2

문제 풀이 IDEA

• 예시 실행

들어올 값	1번들어온 값	나간 값	2번		3번		4번		큐스택
	큐		스택		스택		큐		[]
	1		2		3		4		[]
2	2	1	1	1	1	1	1	4	4
현재 값	2		2		3		1		4
4	4	2	2	2	2	2	2	1	[4,1]
현재 값	4		2		2		2		4,1
7	7	4	4	4	4	4	4	2	4,1,2
현재 값									[4,1,2]

• 스택은 값이 들어왔다 바로 나가기 때문에 리스트로 값을 넣을때만 사용하자.
  • 0 의 개수 만큼 큐를 구현한다.
  • 4번째 줄 만큼 반복문을 돌면서 큐의 append, popleft 를 사용해서 값을 바꿔나간다.
• 2번째 try
  • 스택은 값이 지나가기 때문에 구현하지 않는다.
  • 큐에 해당하는 값들을 가지고 하나의 큐로 만든다.
  • 뒤의 값이 더 먼저 나갈 수 있게 뒤로 배치한다.
  • 새로 들어오는 값들은 appendleft 를 사용해서 왼쪽부터 삽입해준다.
  • 나가야 하는 개수 만큼 오른쪽에서 pop 해서 answer에 넣는다.

문제 풀이 CODE

import sys
from collections import deque

input=sys.stdin.readline

N=int(input())
A=list(map(int,input().split())) # 0,1,1,0
B=list(map(int,input().split()))# 1,2,3,4

queuestack=[]

for idx,value in enumerate(B):
    if A[idx]==0:
        queuestack.append(deque([value]))
    else:
        queuestack.append([value])
        
M=int(input())
C=list(map(int,input().split()))

answer=[]

for i in range(M):
	value=C[i]
	for j in range(N):
		if A[j]==0:
				queuestack[j].append(value)
				value=queuestack[j].popleft()
	answer.append(value)
print(answer)

반복문 2회 사용으로 시간이 초과되었다.

• 정답코드

import sys
from collections import deque

input=sys.stdin.readline
'''
N 자료구조 개수(~100,000)
A : 0 -> 큐 1-> 스택
B : 자료구조에 들어있는 원소 1~10억
M : 삽입할 수열의 길이 ~100000
C : 삽입할 수열. 
'''

N=int(input())
A=list(map(int,input().split())) # 0,1,1,0
B=list(map(int,input().split()))# 1,2,3,4

queuestack=deque()

for idx,value in enumerate(B):
    if A[idx]==0:
        queuestack.append(value)
        
M=int(input()) # 삽입할 수열의 길이. 
C=list(map(int,input().split())) # 수열의 리스트
answer=[]

for i in C:
    queuestack.appendleft(i)

for _ in range(M):
    answer.append(queuestack.pop()) 
print(*answer)