[Python] 백준 24511 queuestack

 

문제 분석

• queuestack 구조는 1번~N번까지의 queue 혹은 stack 이 나열
• 각 자료구조에는 한 개의 원소가 들어있음
• queuestack의 작동 방법
  •  Xn-1번 원소를 N번 자료구조에 삽입(append)하고 N번 자료구조에서 pop한 원소를 Xn
• 최종적인 Xn을 출력

• n : 자료구조의 개수
• 자료구조 개수만큼의 수열 A (각 자료구조가 뭔지 알려줌) : queue(0), stack(1)
• 자료구조 개수만큼의 수열 B : 각 자료구조에 들어있는 원소
• m : 삽입할 수열의 길이
• queuestack에 삽입할 원소를 담고 있는 길이 m의 수열 C

 

코드 설계

• m번 만큼 삽입할거니까 m번 만큼 반복하면서 (i)
• N 만큼 반복하면서 계속 삽입
• 이전에 큐였는지 스택이였는지 ㅇ

 

정답 코드

별거 아닌거 같았는데 생각보다 오래 걸렸다...

 

1차 - 테케는 맞는데 시간초과

import sys
input = sys.stdin.readline

n = int(input())
al = list(map(int, input().split()))
value = list(map(int, input().split()))
'''
qs = [[0]] * n # 이렇게 생성하면 qs의 모든 요소는 같은 리스트 객체를 참조
# 따라서 qs[0][0] = 5 와 같이 값을 변경하면 모든 요소가 같은 리스트를 참조하고 있기 때문에
# 한 곳을 변경해도 나머지도 다 변경
'''

qs = [[0] for _ in range(n)] # 각 요소가 독립된 리스트가 되도록 -> [0]이라는 리스트를 n번 새롭게 생성

for i in range(n):
    qs[i][0] = value[i]

m = int(input())
input_value = list(map(int, input().split()))
ans = []

for i in range(m) :
    x = input_value[i]
    for j in range(n) :
        next_x = -1
        if al[j] == 0 : # queue
            qs[j].append(x)
            next_x = qs[j].pop(0) # 맨 앞
        elif al[j] == 1 :
            qs[j].append(x)
            next_x = qs[j].pop()
        x = next_x
    ans.append(x)

print(' '.join(map(str, ans)))

 

2차 - 덱으로 바꿨는데도 시간 초과

import sys
input = sys.stdin.readline
from collections import deque

n = int(input())
al = list(map(int, input().split()))
value = list(map(int, input().split()))

qs = deque([])

for i in range(n):
    qs.append([value[i]])

m = int(input())
input_value = list(map(int, input().split()))
ans = []

for i in range(m) :
    x = input_value[i]
    for j in range(n) :
        next_x = -1
        if al[j] == 0 : # queue
            qs[j].append(x)
            next_x = qs[j].popleft() # 맨 앞
        elif al[j] == 1 :
            qs[j].append(x)
            next_x = qs[j].pop()
        x = next_x
    ans.append(x)

print(' '.join(map(str, ans)))

M은 최대 1,000,000,000, N은 최대 100,000이기 때문에 이중 for문으로 하면 시간 초과가 날 수밖에 없다.

 

다른 사람 코드 1

• 스택에 원소를 새로 넣었다 빼는 것은 무의미 하다. 따라서 큐만 고려하면 된다
• 큐에 해당하는 원소들을 하나의 큐로 만든다.

import sys
input = sys.stdin.readline
from collections import deque

n = int(input())
list_a = list(map(int, input().split())) # q : 0, s : 1
list_b = list(map(int, input().split())) # 1 2 3 4

m = int(input())
list_c = list(map(int, input().split()))

res = deque()

for i in range(n) :
    if list_a[i] == 0 :
        res.append(list_b[i])

for i in range(m) :
    res.append(list_c[i])
    print(res.popleft(), end=' ')

 

다른 사람 코드 2

https://dduniverse.tistory.com/entry/%EB%B0%B1%EC%A4%80-24511-queuestack-%ED%8C%8C%EC%9D%B4%EC%8D%AC-python

백준 24511 | queuestack [파이썬 python]

from collections import deque
import sys
input = sys.stdin.readline

N = int(input())                    # queuestack을 구성하는 N개의 자료구조
A = list(map(int, input().split())) # 길이 N의 수열 A
B = list(map(int, input().split())) # 길이 N의 수열 B
M = int(input())                    # 삽입할 수열의 길이 M
C = list(map(int, input().split())) # 길이 M의 수열 C

queue = deque([])
for i in range(N):
    if A[i] == 0: # 큐인 자료구조만 모으기
        queue.append(B[i])

# 배열 C의 원소를 1개 appendleft 할 때마다 pop 연산 수행
for i in range(M):
    queue.appendleft(C[i])
    print(queue.pop(), end= ' ')

 

 

2회차 - 25.02.07