백준 구현 대비 피자굽기

문제 : https://www.acmicpc.net/problem/1756

초기 접근

피자는 위에서 부터 떨어진다. 즉, 제일 먼저 떨어지는 피자가 도달한 오븐위에는, 첫 피자 보다 작은 피자들이 차곡 차곡 쌓인다. 다시 말해서, 제일 먼저 떨어져야 하는 피자의 다음 순서에 있는 피자들 중 첫 피자보다 크기가 작은 피자들을 갯수를 count한 후, 첫 피자가 떨어진 인덱스에서 더해주는 식으로 계산하였다. 이 인덱스 값이 0보다 작아지면 모든 오븐에 피자를 담을수 없는 것이므로 0을 출력하면됨.

여기 까지는 굉장히 순조롭다고 생각하였으나, 시간 초과가 발생하였음... 도저히 감이 잡히지 않아 구글링해서 힌트를 얻음ㅠ

초기 코드 (시간 초과 발생)

from collections import deque

d,n=map(int, input().split()) # d는 오븐의 깊이 n의 피자 반죽 갯수
oven=list(map(int, input().split()))
pizza=deque(list(map(int, input().split())))


600000
# last_index 는 
while pizza:
  last_index=d-1
  if last_index<0:
    print(0)
    exit()
  pizza_count=0
  cur_pizza=pizza.popleft()
  pizza_count+=1
  while pizza and pizza[0]<=cur_pizza:
    pizza_count+=1
    pizza.popleft()

  for i in range(d):
    if oven[i]>=cur_pizza:
      last_index=i
    else:
      d=i+1
      break
  last_index-=pizza_count
last_index+=2
print(last_index)

새로운 접근

피자가 위에서 부터 내려오는게 아닌 밑 에서 부터 차곡 차곡 쌓인다는 개념으로 발상을 전환해야함
근데 그럴려면 오븐의 길이들을 내림차순으로 변경해주어야 한다

• 변경 이유 : 변경해주지 않는다면 먼저 들어온 길이가 긴 피자 도우 위에 다음 피자도우가 막혀야 하는 경우임에도 불구하고 그대로 실행이 안되는 경우가 있을수 있으므로 변화시켜 주어야함
  
  이런식으로 출처 : https://hbj0209.tistory.com/198

새로운 코드

import sys
input = sys.stdin.readline
D, N = map(int,input().split())
oven = list(map(int,input().split()))
pizza = list(map(int,input().split()))
# 오븐 깊이가 깊은 곳의 반지름은 그 위보다 항상 같거나 작게 재정렬
for i in range(D-1):
    if oven[i] < oven[i+1]:
        oven[i+1] = oven[i]
 
# cur: 현재 우리가 확인하고자 하는 피자 인덱스
cur = 0
for i in range(D-1, -1, -1):
    # 현재피자의 반지름이 oven의 반지름보다 크면 continue 해줌으로써 i가 다음 오븐반지름 가리킴
    if pizza[cur] > oven[i]:
        continue
    
    # 현재피자의 반지름이 oven[i]의 반지름보다 같거나 작으면 cur 1증가, 다음 피자확인
    # cur이 N이면 모든피자를 오븐에 다 넣은 것이므로 i+1출력
    cur += 1
    if cur >= N:
        print(i+1)
        sys.exit(0)
 
# i가 0까지 왔는데 sys.exit(0)에 걸리지 않았으면 모든 피자를 넣은 것이 아니므로 0출력
print(0)