[Python] 백준 24511 queuestack

문제

길이 M의 수열 C를 가져와서 수열의 원소를 앞에서부터 차례대로 queuestack에 삽입할 것이다. 이전에 삽입한 결과는 남아 있다. queuestack에 넣을 원소들이 주어졌을 때, 해당 원소를 넣은 리턴값을 출력하는 프로그램을 작성

 

queuestack 작동 원리

• x0을 입력받는다.
•  x0을 1번 자료구조에 삽입한 뒤 1번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 x1이라 한다.
•  x1 을 2번 자료구조에 삽입한 뒤 2번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 x2이라 한다.
• ...
•  x{N-1}을 N번 자료구조에 삽입한 뒤 N번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 xN이라 한다.

 

 

입력

• 첫째 줄 :  queuestack을 구성하는 자료구조의 개수 N
• 둘째 줄 : 길이 N의 수열 A
• 셋째 줄 : 길이 N의 수열 B
• 넷째 줄 : 수열의 길이 M
• 다섯째 줄 : queuestack에 삽입할 원소를 담고 있는 길이 M의 수열 C

 

출력

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

 

 

https://www.acmicpc.net/problem/24511

24511번: queuestack

 

 

---

★Keypoint : 큐, 스택

 

큐와 스택 자료구조에 대한 이해를 바탕으로 효율적인 코드를 작성하는 것이 핵심

 

 

<최종 CODE>

import sys
from collections import deque

n = int(sys.stdin.readline().rstrip())
dataStruc = list(map(int, sys.stdin.readline().split()))
first = list(map(int, sys.stdin.readline().split()))
M = int(sys.stdin.readline().rstrip())
new = list(map(int, sys.stdin.readline().split()))
q = deque()
result_list = []
#1인 스택의 경우에는, queue에 들어가지 않고 바로 pop() 되기 때문에 append 하지 않아도 된다.
for i in range(n):
    if dataStruc[i] == 0:
        q.append(first[i])

for j in new:
    q.appendleft(j)
    print(q.pop(), end=' ')

 

 

 

<CODE 설명>

 

문제를 해석하는 데에 생각보다 많은 시간이 걸려 당황했다.

기존의 원소 값에서 각 자리에 있는 자료구조의 특성에 따라 추출되는 값이 다르고 이 값이 다음 자리의 계산에 적용되는 연쇄적인 계산이 필요하다.

문제에서 시키는 그대로 코드를 작성하게 되면, 중첩된 for문을 작성해 시간 초과 문제가 생길 수도 있다. 

뿐만 아니라 매우 어렵다.. 

 

 

 

예제를 직접 풀어보면, 자료 구조가 1인 스택에 해당하는 자리의 계산은 실제로 삽입해야 할 원소가 그대로 pop()된다는 것을 알 수 있다. queue 자료구조를 가진 자리는 원래 있던 값을 pop() 을 한다.

또한, 최종적인 값은 가장 마지막 위치에서 pop 하는 것이므로 pop() 을 해서 결과를 출력하게 되는 것이다.

 

 

 

※popleft() 와 마찬가지로 appendleft() 함수는 파이썬의 collections 모듈에서 제공하는 deque (덱, Double-Ended Queue) 자료구조에 사용되는 메서드 중 하나. appendleft() 함수는 덱의 왼쪽에 원소를 추가하는데 사용!