2023 KAKAO BLIND RECRUITMENT 택배 배달과 수거하기

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/150369

파이썬 소스: https://bit.ly/4aClonc

 

문제를 읽어본 후에, 아래 문장에 생각이 사로 잡히게 되면,

트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다.

‘언제 어느 집을 방문해야 최적화된 방문이 되는가?’라는 관점에서 최적화된 집을 먼저 방문할 지 알고리즘을 찾겠다고 접근하면 문제를 풀기 어렵습니다.

‘배달할 택배 또는 빈 택배 상자가 있는 집은 모두 방문해야 한다’라는 관점에서 문제를 접근해야 합니다. 그러면, ‘먼 집과 가까운 집 중에 어디를 먼저 방문하지?’로 관점이 옮겨 지구요. 그러면, ‘먼 집을 다녀오는 중에, 더 실을 수 있으면, 가까운 집을 들려서, 더 박스를 실을 수 있겠구나?’ 로 생각이 귀결되면, 올바르게 접근한 것입니다.

 이 문제는 트릭이, 모든 택배를 배달하고, 모든 빈 박스를 수거하면서 이동할 때, 최소 거리를 구하는 것입니다. 경로를 구하는 문제가 아닙니다. 같은 최소 거리를 가지는 다양한 경로가 존재할 수 있지만, 이 문제에서는 최소 거리만 구합니다.

여기서 한단계 더 나아가서, 리스트 deliveries와 리스트 pickups를 모두 방문하지 않고, 배달할 택배, 빈 택배 상자가 있는 집만 추려내서, 방문한다면, 문제를 조금 최적화해서 풀 수 있습니다.

dict_deliveries = defaultdict(int) dict_pickups = defaultdict(int) for i in range(0, n):     if deliveries[i] > 0:         dict_deliveries[i] = deliveries[i]     if pickups[i] > 0:         dict_pickups[i] = pickups[i]

딕셔너리 2개를 사용해서, 방문할 필요가 있는 택배, 빈 택배가 있는 집만 딕셔너리에 저장합니다.

 

key_deliveries = list(dict_deliveries.keys()) key_pickups = list(dict_pickups.keys()) key_deliveries.sort(reverse=True) key_pickups.sort(reverse=True)

먼 집부터 방문해야 가까운 집을 중간에 방문할 수 있기 때문에, key값이 큰 순서로 sort(reverse=Ture)로 정렬합니다.

while len(key_deliveries) > 0 or len(key_pickups) > 0:

택배가 배달될 집이 있거나, 빈 택배를 수거할 집이 있는 동안 루프가 실행됩니다. 차에 실을 수 있는 용량 cap에 따라서, 어떤 집의 택배를 모두 배달 했거나, 빈 택배를 모두 수거하면, 해당 집은 리스트 key_deliveries 또는, key_pickups 에서 삭제합니다.

 

local_cap = cap n_deliveries = 0 while local_cap > 0 and len(key_deliveries) > 0:     if local_cap >= dict_deliveries[key_deliveries[0]]:         local_cap -= dict_deliveries[key_deliveries[0]]         n_deliveries = max(n_deliveries, key_deliveries[0])         key_deliveries.pop(0)     else:         dict_deliveries[key_deliveries[0]] -= local_cap         local_cap = 0         n_deliveries = max(n_deliveries, key_deliveries[0])

먼저 택배를 배달하는 코드입니다. 배달할 수 있는 만큼 local_cap 이 0 보다 크고, 배달할 택배가 있는 동안 while룰프가 실행됩니다.

리스트 key_deliveries[0] 에는 항상 제일 먼 집의 위치가 저장되어 있습니다. 그 집의 택배를 모두 실을 수 있으면, key_deliveries.pop(0)해서 그 집을 삭제합니다.

코드를 간단하게 n_deliveries를 구하기 위해서 max()를 사용합니다. 초기값은 0이고 제일 처음 방문한 집이 가장 먼 집이기 때문에, 항상 가장 먼 집의 위치가, n_deliveries에 저장됩니다.

특정 집에 택배를 모두 나를 수 없으면, 일부만 택배를 전달 하구요, 전달한 택배 개수 만큼 그집에서 빼주게 됩니다. 따라서, 더 이상 택배를 실을 수 없으므로, local_cap = 0이 됩니다.

 

빈 박스를 수거해 오는 코드는 택배를 배달하는 코드와 완전히 동일합니다.

local_cap = cap n_pickups = 0 while local_cap > 0 and len(key_pickups) > 0:     if local_cap >= dict_pickups[key_pickups[0]]:         local_cap -= dict_pickups[key_pickups[0]]         n_pickups = max(n_pickups, key_pickups[0])         key_pickups.pop(0)     else:         dict_pickups[key_pickups[0]] -= local_cap         local_cap = 0         n_pickups = max(n_pickups, key_pickups[0])

 

 한대의 트럭으로 최소 이동 거리를 계산하기 위한 값 n_deliveries와 n_pickups를 계산했습니다.

answer += ((max(n_deliveries, n_pickups) + 1) * 2)

위와 같이 둘에 어 먼 집 찾아서 이동거리를 계산합니다. 인덱스 0번에 위치하는 집의 거리는 1이기 때문에, +1을 합니다. 트럭은 왕복 운행임으로, * 2를 해서 answer에 더하게 됩니다.

위의 과정을 첫 while루프가 끝날 때까지 반복하면, 트럭의 최소 이동 거리를 구할 수 있습니다.

 

궁금한 내용은 댓글, 이메일(coding.data.pul@gmail.com)로 보내주세요.

코데풀 유튜브 구독 부탁드립니다.

https://www.youtube.com/@codapul

 

전체 코드는 아래에 있습니다.

from collections import defaultdict from typing import List def solution(cap: int, n: int, deliveries: List[int], pickups: List[int]):     dict_deliveries = defaultdict(int)     dict_pickups = defaultdict(int)     for i in range(0, n):         if deliveries[i] > 0:             dict_deliveries[i] = deliveries[i]         if pickups[i] > 0:             dict_pickups[i] = pickups[i]     key_deliveries = list(dict_deliveries.keys())     key_pickups = list(dict_pickups.keys())     key_deliveries.sort(reverse=True)     key_pickups.sort(reverse=True)     answer = 0     while len(key_deliveries) > 0 or len(key_pickups) > 0:         local_cap = cap         n_deliveries = 0         while local_cap > 0 and len(key_deliveries) > 0:             if local_cap >= dict_deliveries[key_deliveries[0]]:                 local_cap -= dict_deliveries[key_deliveries[0]]                 n_deliveries = max(n_deliveries, key_deliveries[0])                 key_deliveries.pop(0)             else:                 dict_deliveries[key_deliveries[0]] -= local_cap                 local_cap = 0                 n_deliveries = max(n_deliveries, key_deliveries[0])         local_cap = cap         n_pickups = 0         while local_cap > 0 and len(key_pickups) > 0:             if local_cap >= dict_pickups[key_pickups[0]]:                 local_cap -= dict_pickups[key_pickups[0]]                 n_pickups = max(n_pickups, key_pickups[0])                 key_pickups.pop(0)             else:                 dict_pickups[key_pickups[0]] -= local_cap                 local_cap = 0                 n_pickups = max(n_pickups, key_pickups[0])         answer += ((max(n_deliveries, n_pickups) + 1) * 2)     return answer