백준 24511 - queuestack

 

처음 든 생각

- 흠 이게 뭔 소리지 -> 종이에 하나씩 차근차근 써가면서 읽어보니 이해됐다.

- 아 결국 큐에 있는 애들만 원소를 바꿔치기 하면 되겠구나

 

나의 답 

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

N = int(input())
isStack = list(map(int, input().split()))
arr = list(map(int, input().split()))
M = int(input())
new = list(map(int, input().split()))

q = deque()
for i in range(N):
    if isStack[i] == 0:
        q.append(arr[i])
q.reverse()
result= []
for i in new:
    q.append(i)
    result.append(q.popleft())

print(" ".join(map(str, result)))

 

자료구조가 스택인 놈들은 어차피 원소의 값이 바뀌지 않고 처리해줘야할 게 없기 때문에 넘어가면 된다. 결국 자료구조가 큐인 애들만 싹 모아주고 별도의 큐를 만들어준 다음 거기서 하나씩 append하고 popleft 하는 거나 마찬가지다.

 

1번 예제를 통해서 간단하게 살펴보면

[1,4]라는 큐에서 2 4 7이 차례대로 들어오는 것이다.

1 4에서 2라는 애를 새로 추가해서 [ 2 1 4] 로 만들어준 다음 4는 맨 마지막에 pop해서 리턴되는 놈이다. 그래서 1차 결과는 [2 2 3 1]

 

큐 자료구조에서 하나씩 추가하면서 밀어내는 것이 결국 처리될 하나의 공통 로직이다.

 

그래서 for문 한 번만 돌면서 append, popleft만 반복해주면 된다.

 

나의 틀린 답

import sys
input = sys.stdin.readline

N = int(input())
isStack = list(map(int, input().split()))
arr = list(map(int, input().split()))
M = int(input())
new = list(map(int, input().split()))

result = []

for i in new:
    idx = 0
    tmp = i
    while idx<N:
        if isStack[idx] == 0:
            tmp2 = arr[idx]
            arr[idx] = tmp
            tmp = tmp2
        idx += 1
    result.append(tmp)

print(" ".join(map(str, result)))

 

처음에 생각했던 알고리즘은 new에 대해서 하나씩 다 확인해가면서 리턴값을 확인하는 것이었다. 결과는 '시간 초과'였는데 이유는 간단했다. 위의 알고리즘은 최악의 경우 100억번의 연산을 수행해야하기 때문이다. 시간 복잡도 측면을 고려하지 않고 그냥 문제 흐름대로 바로 구현하다가 실패한 케이스였다.

 

조건에 따른 시간복잡도도 고려하면서 알고리즘을 구성하는 연습을 더더 많이 해보자.