js 코딩 테스트 : [ 택배 배달과 수거하기 ]

문제 : 택배 배달과 수거하기 LV.2

문제 설명

당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.
배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n)
트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다. 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.

다음은 cap=4 일 때, 최소 거리로 이동하면서 5개의 집에 배달 및 수거하는 과정을 나타낸 예시입니다.

	집 #1	집 #2	집 #3	집 #4	집 #5
배달	1개	0개	3개	1개	2개
수거	0개	3개	0개	4개	0개

배달 및 수거 과정

16(=5+5+3+3)의 거리를 이동하면서 모든 배달 및 수거를 마쳤습니다. 같은 거리로 모든 배달 및 수거를 마치는 다른 방법이 있지만, 이보다 짧은 거리로 모든 배달 및 수거를 마치는 방법은 없습니다.

트럭에 실을 수 있는 재활용 택배 상자의 최대 개수를 나타내는 정수 cap, 배달할 집의 개수를 나타내는 정수 n, 각 집에 배달할 재활용 택배 상자의 개수를 담은 1차원 정수 배열 deliveries와 각 집에서 수거할 빈 재활용 택배 상자의 개수를 담은 1차원 정수 배열 pickups가 매개변수로 주어집니다. 이때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 return 하도록 solution 함수를 완성해 주세요.

제한사항

• 1 ≤ cap ≤ 50
• 1 ≤ n ≤ 100,000
• deliveries의 길이 = pickups의 길이 = n
  • deliveries[i]는 i+1번째 집에 배달할 재활용 택배 상자의 개수를 나타냅니다.
  • pickups[i]는 i+1번째 집에서 수거할 빈 재활용 택배 상자의 개수를 나타냅니다.
  • 0 ≤ deliveries의 원소 ≤ 50
  • 0 ≤ pickups의 원소 ≤ 50
• 트럭의 초기 위치는 물류창고입니다.

입출력 예

cap	n	deliveries	pickups	result
4	5	[1, 0, 3, 1, 2]	[0, 3, 0, 4, 0]	16
2	7	[1, 0, 2, 0, 1, 0, 2]	[0, 2, 0, 1, 0, 2, 0]	30

내코드 [오답임 : 정답률 95%]

function solution(cap, n, deliveries, pickups) {
    var answer = 0;
    let currentIndex = n

    while(currentIndex > 0) {

        if(deliveries[currentIndex - 1] === 0 && pickups[currentIndex - 1] === 0){
            currentIndex--
            continue
        }

        answer += currentIndex * 2
        let delCount = 0
        let picCount = 0
        let lastIndex = 0

        for (var i = currentIndex; i > 0 ; i--) {
            delCount += deliveries[i - 1]

            if (delCount <= cap || deliveries[i - 1] === 0)
                deliveries[i - 1] = 0
            else {
                deliveries[i - 1] = delCount - cap
            }

            if (delCount > cap) {
                lastIndex < i ? lastIndex = i : ''
                break
            }
        }

        for (var i = currentIndex; i > 0 ; i--) {
            picCount += pickups[i - 1]

            if (picCount <= cap || pickups[i - 1] === 0) 
                pickups[i - 1] = 0
            else { 
                pickups[i - 1] =  picCount - cap
            }

            if (picCount > cap) {
                lastIndex < i ? lastIndex = i : ''
                break
            }
        }

        currentIndex = lastIndex
    }
    return answer;
} 

내 코드 리뷰

일단 테스트 결과 하나를 통과하지 못했고 몇가지 항목의 완료시간이 적지 않은 상태에서 끝 낸 코드이다.

의도 및 설계

첫 반복문에서 lastindex 만큼 반복해서 배달 및 수거를 최대치로 진행하고 그 과정에서 마무리 못한 index 를 저장해서 다음 반복때 적용 함

트럭은 왕복해서 배달 및 수거를 마친다 이때
출발하고 전환점까지 cap 만큼 배달을 마지막 집을 기준으로 순차적으로 배달함
복귀 하는 과정에서도 마지막 집을 기준으로 순차적으로 수거해감
(이 과정이 결국 배달과 수거는 별개의 작업으로 생각함)

따로 변수를 선언해 최대치를 넘어가는 기준으로 여러가지 작업이 일어나게 로직을 설계함

보완해야 하는 부분

배달과 수거 행위의 반복문이 각각 돌기 때문에 반복문을 줄여야 한다

if 문을 많이사용해 가독성이 떨어진다

다른 해결 방법

1. 한번의 왕복 행위에서 배달량과 수거량을 정해두고 각 집마다의 배달 수거 만큼 빼고 남은 잉여량을 다음 로직에서 활용

다른 코드들 중에서 신박했던 부분

배달량과 수거량을 정해두고 잉여량을 그대로 두고 다음 왕복에서 잉여량을 포한한 배달량과 수거량을 계산해 결국 자연스럽게 잉여량까지 효율적 사용하는 간단한 방식이다. (보고 참 놀랬다)

이 방법을 사용한 작성자는 문제를 잘 따져보면 결국 Greedy Algorithms(탐욕법, 탐욕 알고리즘) 로 처리할 수 있다고 보았다
결국 최대치의 배달량과 수거량을 활용하는 것이 아니라 거슬러지는 잔돈을 남기듯 잉여량을 다음 계산에서 처리한다.

Greedy Algorithms(탐욕법, 탐욕 알고리즘) 를 모르기도 했지만 이 코드를 보고 차분히 생각히봐야 그때야 왜 이런 소리를 했는지 이해 함

def solution(cap, n, deliveries, pickups):
    answer = 0

    d = 0
    p = 0

    for i in range(n-1, -1, -1):

        cnt = 0

        d -= deliveries[i]
        p -= pickups[i]

        while d < 0 or p < 0:
            d += cap
            p += cap
            cnt += 1

        answer += (i + 1) * 2 * cnt

    return answer