[Python - 24511] queuestack (S3)

문제

24511번: queuestack

문제

문제

문제

문제 이해

• queuestack : 1, 2, ..., N번의 자료구조(큐 or 스택)가 나열되어 있으며 각 자료구조에는 한 개의 원소가 들어 있음
• queuestack의 작동
  1. x0 입력
  2. x0을 1번 자료구조에 삽입한 뒤 1번 자료구조에서 pop, pop 된 원소는 x1
  3. x1을 1번 자료구조에 삽입한 뒤 1번 자료구조에서 pop, pop 된 원소는 x2
  4. ...
  5. xn-1을 1번 자료구조에 삽입한 뒤 1번 자료구조에서 pop, pop 된 원소는 xn
  6. xn 반환
• 입력받은 M개의 정수(C)를 queuestack에 차례로 삽입했을 때의 반환값(xn)을 출력

출력 예시

자료구조가 어떤 형태인지 글로는 한 번에 와닿지는 않는다. 첫 번째 출력 예시로 확인해 보자.

N = 4
A = [0, 1, 1, 0]
B = [1, 2, 3, 4]
M = 3
C = [2, 4, 7]
>> result : 2 4 7

Ai의 값이 0이면 큐, 1이면 스택이므로 1번과 4번은 큐, 2번과 3번은 스택 구조를 갖고 있다. 또한 B는 queuestack의 초기값이므로 앞에서부터 차례로 1, 2, 3, 4이다. 여기에 C의 값을 하나씩 삽입하며 queuestack의 반환값을 확인하면 2, 4, 7이 나온다.

queuestack

풀이 (1)

N, A, B를 활용해 N개만큼 큐와 스택을 생성하고 초기값을 세팅
C를 차례로 삽입하며 반환값 xn 출력

1. N, A, B, M, C를 차례로 입력받음
2. A, B를 활용해 queuestack 생성
3. C를 순회하며 queuestack에 차례로 삽입 및 반환값 저장
4. 출력

코드

• 스택은 append와 pop을 하면 변화가 없으므로 큐만 고려해도 됨

시간 초과로 인한 여러 시행착오를 거친 코드이다. 이 코드도 시간 초과로 정답 코드는 아니지만, 큐만 고려하여 시간을 단축시켰다.

from collections import deque
import sys

input = sys.stdin.readline

_ = input()
A = input().split()

queuestack = [deque(elem) for qors, elem in zip(A, input().split()) if qors == '0']

_ = input()
C = input().split()

result = []

for x in C:
    xi = x
    for qs in queuestack:
        qs.append(xi)
        xi = qs.popleft()
    result.append(xi)
print(*result)

풀이 (2)

풀이(1) 시간 초과로 고민을 하던 중에 질문게시판에서 이 글을 봤다. 힌트 2를 보자마자 해결 방법이 떠올랐다. 결국 큐만 이어 붙인 경우 마지막 값을 빼고, 맨 위에 삽입한 값을 넣어주면 된다.

도움

큐를 이어 붙인 경우

 

문제에서 주어진 대로 queuestack을 구현하지 않고 결괏값만 동일하게 나오게 작성
풀이 (1)에서 큐만 추출하여 작성했는데, 큐를 이어 붙이면 결국 하나의 큐로 볼 수 있음
또한 스택은 어차피 그대로 반환이 되기에 모두 스택일 경우에 C를 그대로 반환

1. N, A, B, M, C를 차례로 입력받음
2. A, B를 통해 하나의 데크(큐) 생성
3. 모두 stack이어서 데크가 비어있다면 C를 그대로 출력
4. C를 순회하며, pop() 및 appendleft(c의 원소)
5. 출력

코드

queuestack을 큐 하나로 구현하여 시간 초과를 피할 수 있었다.

from collections import deque
import sys

input = sys.stdin.readline

N = int(input())
A = input().split()

queuestack = deque(elem for qors, elem in zip(A, input().split()) if qors == '0')

_ = input()
C = input().split()

result = []

if len(queuestack) == 0:
    print(*C)
else:
    for x in C:
        result.append(queuestack.pop())
        queuestack.appendleft(x)
    print(*result)