99클럽 코테 스터디 30일차 (택배 배달과 수거하기)

오늘의 문제: 프로그래머스 택배 배달과 수거하기

문제 설명

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

프로그래머스

문제 풀이

이 문제는 처음에 알고리즘을 떠올리는게 쉽지 않았다. 문제의 질문하기 페이지에서 힌트를 얻어 그리디 알고리즘으로 문제를 해결하였다. 문제의 첫번째 예시로 어떻게 그리디 한지 설명하려고 한다.

deliveries가 [1, 0, 3, 1, 2], pickups가 [0, 3, 0, 4, 0] 경우

배달할 집 과 픽업할 집의 값이 0이 아닌 값들중 가장 먼 거리를 각각 구한다. 위의 경우 배달할 가장 먼거리가 5, 픽업할 가장 먼거리가 4이다. 

이럴 경우 먼 거리인 5을 먼저 다녀 온다.

• 배달의 경우
  • 가장 먼거리인 5의 집에 2를 배달, 4의 집에 1을 배달, 3의 집에 1을 배달한다.
  • 즉 1 -> 1 -> 2를 배달한다.
• 픽업의 경우
  • 돌아오면서 4의 집에 4를 가지고 돌아온다

첫 배달에 왕복 5인 10을 이동한다. 

다음 배달에서는 배달할 가장 먼거리가 3, 픽업할 가장 먼거리가 2이다.

이 경우 역시 먼거리인 3을 다녀온다.

• 배달의 경우
  • 가장 먼거리인 3의 집에 2를 배달, 1의 집에 1을 배달한다.
  • 즉 1 -> 2를 배달
• 픽업의 경우
  • 돌아오면서 2의 집에 3을 회수한다.

두 번째 배달에 왕복 3인 6을 이동한다.

다음 배달에는 모든 배달할 집과 픽업할 집이 0이기 때문에 

이동거리는 10 + 6인 16이다.

def solution(cap, n, deliveries, pickups):
    answer = 0
    far_deliver = n - 1
    far_pickup = n - 1
    # 트럭이 이동해서 배달하거나 픽업해야할 집이 남아있을 경우
    while far_deliver >= 0 or far_pickup >= 0: 
    # 현재 트럭이 이동해야할 가장 먼 거리 계산
        while far_deliver >= 0:
            if deliveries[far_deliver] == 0:
                far_deliver -= 1
            else:
                break
        while far_pickup >= 0:
            if pickups[far_pickup] == 0:
                far_pickup -= 1
            else:
                break
    # 배달이나 픽업 거리중 가장먼거리 이동(그리디)
        far_length = max(far_deliver, far_pickup)
        answer += (far_length + 1) * 2
    # 배달 처리
        cap_deliver = cap
        while far_deliver >= 0 and cap_deliver > 0:
            temp = min(deliveries[far_deliver], cap_deliver)
            deliveries[far_deliver] -= temp
            cap_deliver -= temp
            if deliveries[far_deliver] == 0:
                far_deliver -= 1
    # 수거 처리
        cap_pickup = cap
        while far_pickup >= 0 and cap_pickup > 0:
            temp = min(pickups[far_pickup], cap_pickup)
            pickups[far_pickup] -= temp
            cap_pickup -= temp
            if pickups[far_pickup] == 0:
                far_pickup -= 1
    return answer