[백준 - python] 24511번: queuestack

문제 링크

24511번: queuestack

문제 풀이

import sys
input = sys.stdin.readline

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):
    if a[i] == 0:
        answer.append(b[i])
answer.reverse()

if answer == []:
    print(*c)
else:
    if m > len(answer):
        for j in range(m - len(answer)):
            answer.append(c[j])
        print(*answer)
    else:
        print(*answer[0:m])

24511 입출력 예시

 

*key point: queuestack 안에 있는 자료구조들 중 스택의 경우, 원소 x를 삽입한 후 pop 하게 되어도 아무런 변화가 없다는 점을 이용한다. 스택인 경우를 무시하고 queuestack을 보게 되면, 결국 삽입한 원소가 appendleft 되고 가장 뒤쪽 원소가 pop되는 하나의 queue임을 알 수 있다. 이를 숙지하고 아래의 순서대로 알고리즘을 구현하였다.

 

1. 수열 A의 원소 중 0(큐)인 인덱스를 찾아서 수열 B의 해당 인덱스의 원소만 가지는 리스트(answer)를 만든 후 뒤집는다 (queuestack에서 원소가 나오는 순서대로 만드는 것) .

2. answer가 비어있는 경우는 queuestack 안의 모든 자료구조가 스택이므로 수열 C가 정답 리스트이다.

3. 그렇지 않은 경우 queuestack 안의 큐 자료구조의 원소가 역순으로 들어가 있는 answer 리스트를 원소의 수에 따라 조건을 나누어 부족한 만큼 수열 C의 원소로 채워주거나 불필요한 부분을 뺀 만큼만 출력한다.

 

 

*trials & comments: 

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
b = list(map(lambda x: deque([int(x)]), input().split()))
m = int(input())
c = list(map(int, input().split()))

result = []
for i in range(m):
    x = c[i]
    for j in range(n):
        if a[j] == 0:
            b[j].append(x)
            x = b[j].popleft()
        elif a[j] == 1:
            b[j].append(x)
            x = b[j].pop()
    result.append(str(x))

print(" ".join(result))

문제 설명을 읽으며 그대로 풀이를 구현한 결과는 위와 같다. 이 경우 2중 for문에 의해 시간 복잡도가 크게 올라가서 시간 초과가 발생했다.

import sys
from collections import deque

input = sys.stdin.readline

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

result = []
for i in range(m):
    x = c[i]
    for j in range(n):
        if a[j] == 0:
            b[j], x = x, b[j]
    result.append(str(x))

print(" ".join(result))

스택인 경우는 생각할 필요가 없음을 깨닫고 append나 pop의 과정 또한 불필요함을 깨달아서 코드를 수정하였으나 아직 2중 for문의 굴레를 벗어나지 못해 시간 초과가 발생했다.