[백준 24511] queuestack - python

💡문제 분석 요약

💡코드

from collections import deque
N=int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
M = int(input())
C = list(map(int, input().split()))

answer=[]

queuestack=[]
for j in range(N):
    queuestack.append(B[j])

for i in range(M):
    x = C[i]
    for j in range(N):
        if not A[j]:
            newx = queuestack[j]
            queuestack[j]=x 
            x=newx

    answer.append(x)

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

알고리즘 설명 그대로 로직을 짜봤다.

M(십만)*N(십만)=백억이라 시간초과가 날 것 같다.

 

공식을 구해보자…

A가 1인 원소는 변화가 없다. stack일 경우 맨 뒤에 삽입되자마자 바로 맨 뒤부터 pop되기 때문이다.

 

A가 0 1 1 0 일 경우,

첫번째 0 에 신규 원소가 들어간 후, 두번째 0에 첫번째 있던 원소가 들어가고, 기존 자리에 있던 원소가 return 된다.

이걸 3번 반복하면 answer이 나온다.

 

A가 0 1 1 0 0 일 경우 12345에 A,B,C가 들어간다면

A2314 → 5 리턴

B23A1 → 4 리턴

C23BA → 1리턴이 될 것이다

 

따라서 자료구조가 queue인 부분에 들어있던 원소는 뒤에서부터 return 되고, 원래 있던 원소가 모두 pop되면 새로 삽입한 원소가 return 된다.

 

그렇다면 답은

A가 0인 원소 뒤에서부터 + 새로 넣는 원소 앞에서 부터 M개까지!

N=int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
M = int(input())
C = list(map(int, input().split()))

answer=[]

for i in range(N-1, -1, -1):
    if not A[i]:
        answer.append(B[i])
for i in range(M):
    answer.append(C[i])

print(' '.join(map(str, answer[:M])))

💡시간복잡도

N+M