[프로그래머스 / 파이썬] 2023 KAKAO BLIND RECRUITMENT 택배 배달과 수거하기

https://school.programmers.co.kr/learn/courses/30/lessons/150369

---

문제 해석

거리가 1 ~ n + 1에 각각 집이 존재한다.

택배 상자를 담을 수 있는 최대 값이 정해진다.

해당 집에 배달할 박스와 수거할 박스가 주어진다.

배달할 박스와 수거할 박스를 모두 가져올 최소의 거리를 구하는 문제이다.

---

문제 풀이

최소의 경로를 도달하기 위해서는 가장 먼 집의 경우부터 해결해 주어야한다.

가장 먼 집부터 탐색하면 배달할 박스와 수거할 박스를 구분할 필요가 없다.

따라서 그리디하게 문제를 해결할 수 있다.

 

> 실패한 방법 (시간 초과)

처음에는 가장 먼 집부터 차례로 cap 값만큼 줄이고, 남은 상자를 추가로 다음 도달할 집에 줄여가며 구현을 했다.

하지만 n^2의 탐색을 하기 때문에 시간초과가 발생하였다.

이를 해결하기 위해 우선순위 큐, 나누기를 사용 등등 해보았지만 최선의 방법으로도 20개 중 3가지 방법은 해결할 수 없었다.

결국 답안 코드를 보고 어느정도 실마리를 찾았다.

 

> 성공한 방법

굳이 매번 요구된 상자를 갱신할 필요가 없다는 것을 깨달았다.

가장 먼 곳부터 탐색하며 배달할 상자와, 수거할 상자를 더해주었다. 이후 배달이나 수거가 필요하다면 cap 만큼 빼주어 배달과 수거를 동시에 하였다. (필요 없을 때 까지 반복) -> 이 거리에서 작업을 했으므로 해당 거리만큼 답을 더해주었다.

이 방법으로 구현한다면 cap 만큼 빼주어 음수가 나오더라도  다음 작업에서 필요로 하는 만큼 자동으로 갱신되게 된다.

---

문제 코드

먼 거리부터 탐색하기 위해 두 배열을 먼저 뒤집고

가장 먼 집부터 탐색하며 필요한 상자들(배달, 수거)을 갱신 d, p에 갱신

 

음수가 될 때 까지 배달, 수거 작업 -> 작업을 할 때 마다 거리를 더하기

(음수가 된 부분에서는 이전 작업에서 남았던 상자 만큼 알아서 작업한 경우가 됨!)

def solution(cap, n, deliveries, pickups):
    deliveries = deliveries[::-1]
    pickups = pickups[::-1]
    answer = 0
    
    d = 0
    p = 0
    
    for i in range(n):
        d += deliveries[i]
        p += pickups[i]
        
        while d > 0 or p > 0:
            d -= cap
            p -= cap
            answer += (n - i) * 2
    return answer

 

---