[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.04.24

1치 - 시간초과

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

n = int(input())
A = list(map(int, input().split())) # 1~N번 자료구조 -- 0 : 큐, 1 : 스택
B = list(map(int, input().split())) # 1~N번 자료구조에 들어있는 원소
M = int(input()) # 삽입할 수 있는 수열의 길이
C = list(map(int, input().split())) # 삽입할 원소를 담고 있는 길이 M의 수열 C

li = []
for i in range(len(B)) :
    li.append(deque([B[i]]))

for idx in range(M) :
    c = C[idx]
    x = c
    for i in range(len(A)) :
        if A[i] == 0 : # 큐
            li[i].appendleft(c)
            x = li[i].pop()

        # else : # 스택일 때는 변화 x
        #     d.append(c)
        #     x = d.pop()

        c = x
    print(x, end=' ')

 

2차 - 시간초과

각 자료구조의 원소는 1개
큐라면 x가 바뀌고, 스택이면 안바뀜

import sys
input = sys.stdin.readline

n = int(input())
A = list(map(int, input().split())) # 1~N번 자료구조 -- 0 : 큐, 1 : 스택
B = list(map(int, input().split())) # 1~N번 자료구조에 들어있는 원소
M = int(input()) # 삽입할 수 있는 수열의 길이
C = list(map(int, input().split())) # 삽입할 원소를 담고 있는 길이 M의 수열 C

for idx in range(M) :
    c = C[idx]
    for i in range(len(A)) :
        if A[i] == 0 : # 큐
            tmp = B[i]
            B[i] = c
            c = tmp
    print(c, end=' ')

이중 for문 시간초과

 

3차 - 25.06.26

• 자료구조가 stack이라면 pop했을 때 [-1]일 것이고, queue라면 [0]일 것
• stack 인 경우에는 넣었다가 다시 그대로 값을 pop하므로 고려할 필요가 없다.
• 즉, 큐인 경우에만 고려하면 된다.
  
  
• 큐인 자료구조만 남긴 리스트 생성

(1) 틀림

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

N = int(input())
sq = list(map(int, input().split())) # stack(1) or queue(0)
li = deque(list(map(int, input().split())))
M = int(input())
nums = list(map(int, input().split()))

ans = []

# 큐인 자료구조만 남긴 리스트 생성
q = sq.count(0)

for n in nums:
    li.append(n)
    for i in range(q) :
        tmp = li.popleft()
        li.append(tmp)
    a = li.pop()
    ans.append(a)

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

• 모든 자료구조를 하나의 덱(li)로 취급
• 하지만 문제는 서로 다른 N개의 자료구조가 존재하고, 각 구조에는 각각 하나의 값만 들어있다.
  
  
• 큐인 경우에만 값이 바뀐다.

 

(2) 시간초과

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

N = int(input())
sq = list(map(int, input().split())) # stack(1) or queue(0)
li = deque(list(map(int, input().split())))
M = int(input())
nums = list(map(int, input().split()))

queue_li = []
ans = []

# 큐의 위치만 알면 됨
for i in range(N) :
    if sq[i] == 0 :
        queue_li.append(i)

# 큐의 위치마다 해당 위치의 자료구조 값으로 바뀜
for x in nums:
    for i in queue_li :
        tmp = li[i]
        li[i] = x
        x = tmp
    print(x, end=' ')

• 위 코드의 시간복잡도 초과는 다음 코드에서 난다.

for x in nums :
    for i in queue_li :

• nums 의 최대 길이 M
• queue_li 의 최대 길이 N
• O(M x N) = O(10만 x 10만) = 10^10 
  
  
• queue만 따로 추려서 그 흐름만 유지하는 전용 큐만 관리
• queue_li를 통해 실제 필요한 queue 들만 deque로 관리하고, 삽입/삭제 구조만 유지하면 된다.

 

(3) 정답 코드

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

N = int(input())
A = list(map(int, input().split())) # stack(1) or queue(0)
B = list(map(int, input().split()))
M = int(input())
C = list(map(int, input().split()))

d = deque()
ans = []

# 큐의 영향을 받는 값만 덱에 넣기
for i in range(N) :
    if A[i] == 0 :
        d.append(B[i])

for num in C :
    d.appendleft(num) # 맨 앞에 넣기
    print(d.pop(), end=' ')