[프로그래머스] 택배 배달과 수거하기 (2023 KAKAO BLIND RECRUITMENT) - Python

2023 KAKAO BLIND RECRUITMENT - Lv2.

🌵 문제

---

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

프로그래머스

 

 

🚀 풀이

---

처음에는 O(N^2) 정도의 풀이밖에 생각이 안났는데, input인 n 범위 보니까 각이 안나오더라고요.. 그래서 좀 결이 다르긴 하지만 아래 구명보트 문제 푼 것처럼 조건에 만족하는 친구, task가 다 해결된 친구를 하나씩 보내주는 (신경꺼주는) 그리디한 방식은 어떨까 생각했습니다. 

 

[프로그래머스] 구명보트 - Python

 

일단 트럭에 수량은 늘 꽉꽉 담고 다닌다고 생각하고, 가장 먼 집부터 살펴봅니다.

 

맨 끝 집의 배달과 수거가 끝나기 위해서 몇 번 왔다갔다 해야하는지 체크합니다. 이를 deliver_cnt와 pickup_cnt로 두고 반복문을 돌리는데, 배달 수량과 수거 수량이 각각 모두 소진되었을 때를 기준으로 종료조건을 뒀습니다. 횟수 체크를 위함이니까 실제 수량에서 빼버리면 안되니까, temp도 뒀습니다. (수량은 생각하기 편하라고 남은 deliver 수량은 양수로, 남은 pickup 수량은 음수로 관리하고, 소진되는 조건 체크도 deliver 수량은 0보다 작거나 같을 때 + pickup 수량은 0보다 크거나 같을 때로 설정했습니다.) 

 

그리고 나서 나온 deliver_cnt와 pickup_cnt 중 더 큰 값 (둘 다 task가 소진되어야 하기 때문) 을 선택해 맨 끝 집에서의 이동 횟수를 결정했고 (cnt), 맨 끝 집을 정복하기까지의 이동 거리를 총 거리에 더해줍니다. (distance += (i + 1) * cnt * 2) 왔다 갔다가 한 세트니까 곱하기 2도 해줍니다. 

 

for문 내부에서 remain_deliver과 remain_pickup을 0으로 초기화해주지 않고 기존 값을 그대로 쓰는 건, 남은 물품은 오는 길에 채우거나 수거하고 올 수도 있기 때문입니다. 이렇게 가장 센터와 가장 가까운 집까지 돌고 나면 이동한 최소거리를 얻을 수 있습니다. 

 

---

💡 풀이 코드는 아래와 같습니다. 

def solution(cap, n, deliveries, pickups):
    distance = 0  # 최종 거리
    remain_deliver = 0
    remain_pickup = 0
    for i in range(n - 1, -1, -1):  # 가장 먼 집부터 정복
        remain_deliver += deliveries[i]  # 현재 보고 있는 집 까지의 남은 배달 수, 양수로 관리
        remain_pickup -= pickups[i]  # 현재 보고 있는 집 까지의 남은 수거 수, 음수로 관리

        deliver_cnt = 0
        pickup_cnt = 0
        temp_deliver = remain_deliver  # deliver count 체크를 위한 임시 remain_deliver
        temp_pickup = remain_pickup  # pickup count 체크를 위한 임시 remain_pickup
        # 현재 보고 있는 집의 task 가 소진 되기 까지의 과정, 0 기준 조건 만족 (소진)
        while True:
            if temp_deliver <= 0:
                break
            temp_deliver -= cap
            deliver_cnt += 1
        while True:
            if temp_pickup >= 0:
                break
            temp_pickup += cap
            pickup_cnt += 1

        # cnt: 처리 해야 하는 남은 물품 없이 다녀 와야 하는 횟수, 둘 중 더 큰 수로 결정
        cnt = max(deliver_cnt, pickup_cnt)
        remain_deliver -= cnt * cap
        remain_pickup += cnt * cap
        distance += (i + 1) * cnt * 2  # 거리 더하기 (왕복)
    return distance