[SWEA][D3][#05099] 피자 굽기

출처

• SW Expert Academy

학습용 포스트입니다. 본 포스트가 문제가 될 시 수정 또는 삭제하겠습니다.

문제

N개의 피자를 동시에 구울 수 있는 화덕이 있다. 피자는 치즈가 모두 녹으면 화덕에서 꺼내며, 치즈의 양은 피자마다 다르다.

1번부터 M번까지 M개의 피자를 순서대로 화덕에 넣을 때, 치즈의 양에 따라 녹는 시간이 다르기 때문에 꺼내지는 순서는 바뀔 수 있다.

주어진 조건에 따라 피자를 구울 때, 화덕에 가장 마지막까지 남아있는 피자 번호를 알아내는 프로그램을 작성하시오.

그림 생략

• 피자는 1번위치에서 넣거나 뺄 수 있다.

• 화덕 내부의 피자받침은 천천히 회전해서 1번에서 잠시 꺼내 치즈를 확인하고 다시 같은 자리에 넣을 수 있다.

• M개의 피자에 처음 뿌려진 치즈의 양이 주어지고, 화덕을 한 바퀴 돌 때 녹지않은 치즈의 양은 반으로 줄어든다. 이전 치즈의 양을 C라고 하면 다시 꺼냈을 때 C//2로 줄어든다.

• 치즈가 모두 녹아 0이 되면 화덕에서 꺼내고, 바로 그 자리에 남은 피자를 순서대로 넣는다.

입력

첫 줄에 테스트 케이스 개수 T가 주어진다. 1<=T<=50

다음 줄부터 테스트 케이스의 첫 줄에 화덕의 크기 N과 피자 개수 M이 주어지고, 다음 줄에 M개의 피자에 뿌려진 치즈의 양을 나타내는 Ci가 주어진다.

3<=N<=20, N<=M<=100, 1<=Ci<=20

출력

각 줄마다 “#T” (T는 테스트 케이스 번호)를 출력한 뒤, 번호를 출력한다.

예제

입력

3
3 5
7 2 6 5 3
5 10
5 9 3 9 9 2 5 8 7 1
5 10
20 4 5 7 3 15 2 1 2 2

출력

#1 4
#2 8
#3 6

My Sol

from collections import deque

def pushPizzaToOven():
    global oven, pizzas, M
    if M:
        oven.append(pizzas.popleft())
        M -= 1
        return 1
    return 0

T = int(input())
for tc in range(1, T+1):
    N, M = map(int, input().split())
    inp = list(map(int, input().split()))
    inp2 = []
    for i, n in enumerate(inp):
        inp2.append((i+1, n))

    pizzas = deque(inp2)
    oven = deque()


    # 처음에 피자 오븐 크기만큼 넣기
    for _ in range(N):
        pushPizzaToOven()

    # 화덕 가동
    while N > 1:
        idx, val = oven.popleft()
        # 제일 오래된 피자 꺼내기
        check = val // 2

        # 치즈 남았다면
        if check:
            oven.append((idx, check))

        # 치즈가 다 녹았다면
        else:
            # 남은 피자가 있다면 넣고, 아니라면 N을 1 빼줌
            if not pushPizzaToOven():
                N -= 1

    print(f'#{tc} {oven.pop()[0]}')

deque를 이용해서 피자 목록에서 화덕에 피자를 하나하나 넣어주었고, 마지막까지 치즈의 양이 남아있는 피자의 번호를 출력하면 되었다. 그런데 피자 치즈의 양을 직접적으로 건드려야 하기 때문에 모든 deque가 빠져나가고 하나만 남았을 때 이 피자가 어떤 피자인지 알아내는 것이 중요했고, 처음에 deque에 피자를 담을 때 치즈의 양과 함께 피자의 번호를 tuple로 넣어 이를 oven에서 이를 반씩 줄이는 연산을 처리하고 다시 피자 번호와 함께 tuple로 append하는 방식을 사용했다. 이러면 치즈의 양은 양대로 체크할 수 있고, 피자의 번호 역시 판별이 가능하다.

결과

PASS