2학년 2학기 알고리즘 과제_4주차(백준_24511번:queuestack)

24511번: queuestack

 

 

문제

한가롭게 방학에 놀고 있던 도현이는 갑자기 재밌는 자료구조를 생각해냈다. 그 자료구조의 이름은 queuestack이다.

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

queuestack의 작동은 다음과 같다.

•  x0$x_0$을 입력받는다.
•  x0$x_0$을 1$1$번 자료구조에 삽입한 뒤 1$1$번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 x1$x_1$이라 한다.
•  x1$x_1$을 2$2$번 자료구조에 삽입한 뒤 2$2$번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 x2$x_2$이라 한다.
• ...
•  xN−1$x_{N-1}$을 N$N$번 자료구조에 삽입한 뒤 N$N$번 자료구조에서 원소를 pop한다. 그때 pop된 원소를 xN$x_N$이라 한다.
•  xN$x_N$을 리턴한다.

도현이는 길이 M$M$의 수열 C$C$를 가져와서 수열의 원소를 앞에서부터 차례대로 queuestack에 삽입할 것이다. 이전에 삽입한 결과는 남아 있다. (예제 1$1$ 참고)

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

 

입력

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

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

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

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

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

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

 

 

출력

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

 

 

 

 

📌 내풀이

 

해당 문제 제목부터가 큐와 스텍과 관련한 문제일 것이라 생각했는데, 자료구조와 관련된 내용을 말하고 있다.

도현이가 생각한 재미있는 자료구조인 queuestack의 구조는 다음과 같다. 1부터 N번의 자료구조가 나열되어있으며, 각각 자료구조에는 한개의 원소가 들어있다.

 

큐와 스택의 자료구조를 합쳐놓았을 때 프로그램이 어떻게 작동하는지 묻는 문제인 것 같다.

 

 

관련된 내용을 이해하기위해 찾아보았다.

• 먼저 첫째줄에는 자료구조의 개수 n이 주어진다.
• 이후 n개의 수열 A가 주어지는데, 0이면 큐, 1이면 스택을 나타낸다.
• 다음 줄에는 각 자료구조에 들어있는 원소들이 나타난다.
• 예를 들어 두번째 줄에 '0 1 1 0', 세번째 줄에 '1 2 3 4'가 주어진다면
  1은 첫번째 자료구조인 큐에, 2는 스택, 3도 스택, 4는 큐에 저장되는 것이다.
• 물론 각각의 자료구조에 따로 저장되는 구조이다.
• 넷째줄에는 삽입할 수열의 길이 m이 주어진다.
• 마지막 줄에는 m길이의 수열 c가 주어진다. 해당 수열은 문제에서 주어진 queuestack이라는 새로운 자료구조에 삽입하는 것이다.
• queuestack에 삽입하면 해당 원소는 첫번째 자료구조부터 마지막 자료구조까지 돌아가며 순서대로 pop된 원소가 다음 자료구조에 들어간다. 마지막 자료구조에서 pop된 원소가 출력된다.

stack에서는 새롭게 append한 원소가 그대로 pop이 되고, queue에서는 가장 처음에 append된 원소가 pop된다는 것을 이용하여 코드를 작성하면 될 것이다.

 

📌 코드 분석

 

import sys
from collections import deque

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

lst = deque()
for i in range(n):
    if a[i] == 0:
        lst.append(b[i])

for j in range(m):
    lst.appendleft(c[j])
    
for _ in range(m):
    print(lst.pop(), end=' ')

 

 

• n: 리스트 a와 b의 길이이다.
• a: 첫 번째 리스트로, n개의 정수를 포함하고 있다.
• b: 두 번째 리스트로, n개의 정수를 포함하고 있다.
• m: 리스트 c의 길이이다.
• c: m개의 정수를 포함하는 리스트를 의미한다.

lst = deque()

 

• 빈 덱 lst를 초기화한다.
• a[i] 값이 0인 경우에만 b[i] 값을 lst 덱의 오른쪽 끝에 추가(append)하는데, 이 단계에서는 a 리스트를 조건으로 사용하고 b 리스트의 값을 추가하도록 한다.
• 리스트 c의 각 요소를 덱 lst의 왼쪽 끝에 추가(appendleft)한다.
• 그렇기때문에 리스트 c의 모든 값이 덱의 앞쪽에 추가된다.
• 덱에서 오른쪽 끝 요소를 pop하여 출력한다.
• 이 과정은 m번 반복되므로, 덱 lst에서 마지막 m개의 요소가 오른쪽 끝부터 하나씩 출력된다.

 

요약

 

• a 리스트에서 0인 위치를 기준으로 b 리스트의 해당 위치 값을 덱 lst에 추가한다.
• 리스트 c의 모든 요소를 덱의 왼쪽에 추가한다.
• 덱의 오른쪽 끝에서 m개의 요소를 꺼내어 순서대로 출력한다.

 

 

 

📌 느낀점

 

 

첫번째문제에 비해 접근자체가 조금 어려웠다. 문제를 이해하는 것 자체가 쉽지 않았던 것 같다. 같은 자료구조내용인데, 확실히 알고리즘 문제를 푸는데에 자료구조 공부가 얼마나 중요한지 다시한번 느낄 수 있었다..

 

 

 

[ 참고 자료 ]

https://velog.io/@jeyang0319/Python-%EB%B0%B1%EC%A4%80-24511-queuestack-2c2apjee

[Python] 백준 24511 queuestack

 

[Python] 백준 24511 queuestack

[Python] 백준 24511 queuestack