[SW Expert Academy] 5099번 피자굽기 python

문제의 저작권은 SW Expert Academy에 있습니다.

파이썬 SW문제해결 기본 - Queue

문제

N개의 피자를 동시에 구울 수 있는 화덕이 있다. 피자는 치즈가 모두 녹으면 화덕에서 꺼낸다. 1번부터 M번까지 M개의 피자를 순서대로 화덕에 넣을 때, 치즈의 양에 따라 녹는 시간이 다르기 때문에 꺼내지는 순서는 바뀔 수 있다. 주어진 조건에 따라 피자를 구울 때, 화덕에 가장 마지막까지 남아있는 피자 번호를 알아내는 프로그램을 작성하시오.

해설

Queue 자체 라이브러리 보다 deque를 쓰는게 빠르다. 그러니 bfs 풀때는 deque를 아래 처럼 쓰자. 사실 지금 풀이는 여러수정을 거쳐서 좀 복잡하게 만들었다. 다음에 다시 풀어서 올리겠다.

우리가 구해야 하는것은 남은 치즈의 양이 아닌 피자의 번호이다. 기본적으로 접근은 치즈의 양을 deque에 넣는 것이 아닌 '치즈의 양이 적혀있는 list의 index'를 넣었다. 그래서 하나씩 빼서 인덱스 값에 맞는 값을 찾아가서 치즈의 양을 계산하고 0이 아닌 경우는 다시 넣고, 0이면 아직 들어가지 않은 피자를 넣었다.

이때 새로운 피자를 넣기 위해서 새로운 피자의 위치의 인덱스를 담고 있는 last라는 변수를 하나 설정해서 썼다. 

import collections

TC = int(input())
for tc in range(1, TC+1):
    N, M = map(int, input().split())
    data_i = [i for i in range(M)]
    data = list(map(int, input().split()))
    deq = collections.deque()
    last = N-1
    while len(deq) < N:
        a = data_i.pop(0)
        deq.append(a)
        if len(data_i) == 0:
            break
    while len(deq) >= 1:
        idx_i = deq.popleft()
        data[idx_i] = data[idx_i]//2
        if data[idx_i] == 0:
            last += 1
            if last >= M:
                continue
            deq.append(last)
        else:
            deq.append(idx_i)
    print("#%d %d"%(tc, idx_i+1))