[백준/파이썬]24511 queuestack

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

24511번: queuestack

문제

백준24511번 queuestack

 

제시된 원소가 하나씩 밖에 없어서 헷갈렸던 문제다...

 

여러 개의 큐가 하나의 큰 큐가 된다는 것만 이해한다면 쉽게 풀 수 있는 문제다.

 

 

예제 입력 1을 예시로

 

두번째 입력 0 1 1 0을 보면

1번 4번만 큐이고 3번 4번은 스택이다.

 

그다음 각 자료구조에 들어있는 원소들은

1 2 3 4

 

삽입될 원소들은 2 4 7

 

queuestack작동 방법을 문제에서 참고해서 하나씩 해보면

 

2가 입력되었을때,

첫 번째 자료구조인 1에 2가 삽입되어야 하니 [1, 2]가 된다. 여기서 이 자료구조는 큐 이므로 먼저 들어있던 1이 pop 된다.

 

두 번째 자료구조인 2에 1이 다시 삽입된다. [2, 1]이 되고 이 자료구조는 스택이니 마지막에 들어온 1이 pop 된다.

 

세 번째 자료구조인 3에 1이 삽입된다. [3, 1]이 되고 이 자료구조는 스택이니 마지막에 들어온 1이 pop 된다.

 

네 번째 자료구조인 4에 1이 삽입된다. [4, 1]이 되고 이 자료구조는 큐이니 먼저 들어있는 4가 pop 된다.

 

즉 첫 번째 원소 삽입 후에 수열 B는

[2, 2, 3, 1]이 되고 마지막에 pop 된 숫자는 1이 된다.

 

따라서 아래와 같은 수열 B들이 만들어지게 된다.

• 초기 상태 : [1,2,3,4]
• 첫 번째 원소 삽입 : [2,2,3,1]
• 두 번째 원소 삽입 : [4,2,3,2]
• 세 번째 원소 삽입 : [7,2,3,4]

 

위에처럼 해보니 스택은 무시해도 된다고 생각하고 문제를 풀어보았다.

 

오답

def queuestack(x) :
    num = None
    for j in range(n) :
        if qORs[j] == 0 :
            if num != None :
                arr[j], num = num, arr[j]
            else :
                num = arr[j]
                arr[j] = x
    if num == None :
        return x
    else :
        return num

n = int(input())
qORs = list(map(int, input().split()))
arr = list(map(int, input().split()))
m = int(input())
inputArr = list(map(int, input().split()))

ans = []
for i in range(m) :
    ans.append(str(queuestack(inputArr[i])))

print(' '.join(ans))

 

수열 B의 최대 길이가 10억

수열 C의 최대 길이도 10억

 

10억*10억 돌렸으니 시간초과가 나온다

 

그래서 중첩으로 반복하지 않고 문제를 해결할 수 있는 방법을 찾아봤다.

 

https://burningfalls.github.io/algorithm/boj-24511/

[BOJ 24511] 백준 24511번 - queuestack

 

이 블로그를 참고했다.

 

그림을 보니 딱 이해가 됐다.

 

위 블로그의 그림 3처럼 여러 개의 큐를 하나의 큐로 생각하면 되는 문제였다.

 

정답

from collections import deque

n = int(input())
qORs = list(map(int, input().split()))
arr = list(map(int, input().split()))
m = int(input())
inputArr = list(map(int, input().split()))

queue = deque()

for i in range(n) :
    if qORs[i] == 0 :
        queue.appendleft(arr[i])

for n in inputArr :
    queue.append(n)
    print(queue.popleft(), end=' ')