(큐) 피자굽기
2020. 2. 18. 17:31ㆍ개발노트
이 문제의 저작권은 SW Expert 아카데미에 있습니다.
문제는 위 링크에서 확인할 수 있습니다.
쉽게 풀기위해 파이썬에서 제공하는 deque 모듈을 사용했습니다.
화덕의 크기가 N으로 정해져 있기 때문에 deque(maxlen = N)으로 했습니다.
화덕(q)에 아무것도 없는 동시에 화덕에 넣을 피자(Ci)가 남아 있어야 q에 append 하도록 했습니다.
이때 화덕이 한 바퀴를 돌기 때문에 appendleft를 사용해 q의 맨 앞에 요소를 추가했습니다.
화덕(q)에 피자가 모두 들어있다면 q.rotate를 이용해 화덕을 회전시킵니다.
예를 들어 q.rotate(1)을 하면 모든 요소가 오른쪽으로 1칸씩 이동합니다. (맨 뒤의 요소는 맨 앞으로 이동합니다.)
화덕이 회전되었다면 치즈가 모두 녹았는지 판단합니다.
만약 모두 녹아서 피자의 치즈 // 2 가 0이면 화덕에서 꺼냅니다.
q.popleft()를 이용해서 화덕 입구에 있는 피자를 꺼낼 수 있습니다.
치즈가 모두 녹지 않았다면 다시 화덕에 넣습니다. (치즈가 녹았기 때문에 치즈 양을 치즈 // 2로 바꿔줍니다.)
화덕에서 가장 마지막까지 남아있는 피자의 순서를 구해야 하기 때문에
M - 1 만큼 화덕에서 피자를 빼고 단 하나의 피자가 남았을 때 출력합니다.
저는 화덕(q)에 넣을 때 index를 함께 적어서 넣어줬기 때문에 q[0][1]로 순서를 확인했습니다.
from collections import deque
for t in range(int(input())):
N, M = map(int, input().split())
Ci = list(map(int, input().split()))
q = deque(maxlen=N)
q_pop_cnt = 0
cnt = 0
while 1:
if q_pop_cnt == M - 1:
print(f"#{t+1} {q[0][1]+1}")
break
if len(q) < N and len(Ci) > 0:
q.appendleft([Ci[0], cnt])
Ci.pop(0)
cnt += 1
else:
q.rotate(1)
if q[0][0] // 2 == 0:
q.popleft()
q_pop_cnt += 1
else:
q[0][0] = q[0][0] // 2