[Python] 백준 1092번 : 배

https://www.acmicpc.net/problem/1092

1092번: 배

[ 내 코드 ] 

n = int(input())
n_list = list(map(int, input().split()))
m = int(input())
m_list = list(map(int, input().split()))

n_list.sort(reverse=True)
m_list.sort(reverse=True)

print(n_list)
print(m_list)

count = 0
for i in range(len(m_list)):
  for j in range(len(n_list)):
    if (n_list[i] >= m_list[j]):
      del m_list[i]
      break
    print(m_list)

 

[ 클린 코드 ] 

import sys

n = int(input())
cranes = list(map(int, input().split()))

m = int(input())
boxes = list(map(int, input().split()))

# 모든 박스를 옮길 수 없는 경우
if max(cranes) < max(boxes):
  print(-1)
  sys.exit()

# 각 크레인이 현재 옮겨야 하는 박스의 번호 (0부터 시작)
positions = [0] * n
# 각 박스를 옮겼는지의 여부
checked = [False] * m
# 최적의 해를 구해야 하므로, 내림차순 정렬
cranes.sort(reverse=True)
boxes.sort(reverse=True)

result = 0
count = 0

while True:
  if count == len(boxes): # 박스를 다 옮겼다면 종료
    break
  for i in range(n): # 모든 크레인에 대하여 각각 처리
    while positions[i] < len(boxes):
      # 아직 안 옮긴 박스 중에서, 옮길 수 있는 박스를 만날 때까지 반복
      if not checked[positions[i]] and cranes[i] >= boxes[positions[i]]:
        checked[positions[i]] = True
        positions[i] += 1
        count += 1
        break
      positions[i] += 1
  result += 1

print(result)

• 모든 박스를 배로 옮기는데 드는 시간의 최솟값을 계산해야 한다.
• 매 분마다, 모든 크레인에 대하여 옮길 수 있는 박스를 선택하여 옮기도록 한다.
• 박스를 무게 기준으로 내림차순 정렬한 뒤에, 무거운 것부터 옮기도록 하면 된다.
• 시간 복잡도 O(NM)에 문제를 해결할 수 있다.