[ALGO/Python] 1756. 피자 굽기

001. 생각 정리

목표: 오븐을 한 번 이내로 순회하면서 각 피자 반죽의 위치 결정하기

1. 오븐으로 주어진 리스트를 조작하여 실질적인 오븐을 표현하였습니다.
2. 오븐의 최하단에서부터 순회를 시작하여 각 피자 반죽이 위치할 수 있는지 판단하였습니다.
   1. 특정 깊이에서의 오븐 지름이 피자 반죽의 지름보다 길거나 같다면, 해당 피자 반죽은 위치할 수 있습니다.
3. 오븐의 순회를 마친 후에도 피자 반죽이 남아 있다면, 문제에서 요구한 대로 "0"을 출력하였습니다.
   
   

001.1. 실질적인 오븐

특정 깊이에서의 지름은 실질적으로 상단의 지름 중 가장 짧은 지름입니다. 만약 피자 반죽의 지름이 상단의 가장 짧은 지름보다 길다면 해당 깊이에 도달할 수 없습니다.

001.2. 오븐 순회

피자 반죽이 위치할 수 있는 깊이 중 가장 깊은 깊이부터 고려하기 위해 오븐의 최하단에서부터 순회를 시작하였습니다. 특정 깊이에서의 오븐 지름이 현재 다루고 있는 피자 반죽의 지름보다 길거나 같다면, 해당 피자 반죽을 위치시킵니다. 이는 최종적으로 출력할 값을 갱신하는 방식으로 구현하였습니다. 또한 다음 피자 반죽을 다루기 위해 피자로 주어진 리스트에 접근하는 인덱스를 한 단위 증가시켰습니다.

001.3. 남아 있는 피자 반죽

오븐 순회를 마쳤으나 피자 반죽에 접근하는 인덱스 값이 전체 피자 반죽 개수와 일치하지 않는다면, 오븐에 들어가지 않은 피자 반죽이 아직 남아 있다는 뜻입니다. 따라서 문제의 요구사항대로 "0"을 출력하였습니다.

002. 코드

import sys


D, N = map(int, sys.stdin.readline().split())
oven = list(map(int, sys.stdin.readline().split()))
pizza = list(map(int, sys.stdin.readline().split()))

# 1. 실질적인 오븐을 표현
for d in range(1, D):
    oven[d] = min(oven[d], oven[d-1])

# 2. 최하단에서부터 순회를 시작하여 위치 가능 여부 판단
depth, p_idx = D, 0
for d in range(D-1, -1, -1):
    if p_idx == N:
        print(depth)
        break

    # 2.1. 오븐 지름이 피자 반죽의 지름보다 길거나 같다면, 위치 가능
    if oven[d] >= pizza[p_idx]:
        depth = d + 1
        p_idx += 1
else:
    # 3. 피자 반죽이 남아 있다면, "0" 출력
    print(0)

End