[백준/Python] 24511 - queuestack

문제

한가롭게 방학에 놀고 있던 도현이는 갑자기 재밌는 자료구조를 생각해냈다. 그 자료구조의 이름은 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에 삽입했을 때의 리턴값을 공백으로 구분하여 출력한다.

---

풀이
시간초과때문에 애를 많이 먹었던 문제이다
큐와 스택의 특징을 잘 이용해야하는데, 기본적으로 가장 먼저 고려해야하는 것은 스택의 경우 LIFO로 후입선출의 구조이기 때문에 append하고 pop을 해봤자 스택 내부에 변화가 생기지 않는다
따라서 이 문제에서 스택은 아예 없는 셈 쳐도 상관이 없다
다음으로는 단순히 n $\times$ m을 하면서 모든 경우를 따지게 되면 시간초과가 날 수 밖에 없도록 범위가 주어져있다
따라서 다른 방법을 고민해봐야하는데, 주어진 예제를 가지고 정답의 출력 과정을 고려해보면 금방 떠올릴 수 있다
예를 들어, 예제가 다음과 같다면

4
0 1 1 0
1 2 3 4
3
2 4 7

현재 큐는 1과 4의 값을 가지고 있다 첫 번째 입력값은 2이기 때문에 첫 번째 큐에서 1이 나오고 2가 첫번째 큐로 들어간다
첫번째 큐에서 나온 1은 다시 두번째 큐에 들어가고 4가 나온다
따라서 첫 번째 출력값이 4가 된다.
두 번째 입력값 4과 마지막 입력값 7까지 넣으면 차례대로 4 1 2의 답이 나오게 되는데, 굳이 다른 수들을 모두 넣지 않더라도 출력이 4 1 2가 됨을 알 수 있다

 2   4
 ↓   ↓
[1] [2]
[4] [1]
     ↓
     4

이렇게 원래 큐에 있던 값들이 밀려나오는 구조이기 때문에 큐에 있던 값들을 뒤집은 수와 c의 입력값을 합쳐주면 된다
[4,1]+[2,4,7]
그리고 길이가 m이 되도록 만들어주면 정답이 된다

풀이를 모르겠을 땐 직접 그려보자는 교훈을 새삼 다시 얻었다 ..

코드

import sys
from collections import deque

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
b = list(map(int, sys.stdin.readline().split()))

m = int(sys.stdin.readline())
c = list(map(int, sys.stdin.readline().split()))

result = []
for i, elem in enumerate(b):
    if a[i] == 0:
        result.append(elem)
result.reverse()

for elem in c[:m-len(result)]:
    result.append(elem)
print(*result[:m])