[프로그래머스lv2] 택배 배달과 수거하기 JS

 

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

 

 

 

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

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

 

 

 

 

첫번째 풀이 (성공)

문제 정리

• n개 집, 최대 cap개 적재할 수 있다
• 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구해라

문제이해

• 가장 먼 곳부터 가까운 곳까지 이동하며 배달과 수거를 완료한다.
• 창고에서 i번째 집까지 가는 길에 cap개를 배달하고, 돌아오는 길에 cap개를 수거할 수 있다. 
• 배달해야할 가장 먼 집과, 수거해야할 가장 먼 집 중 더 먼 곳의 2배가 한 번 왕복 이동거리이다
• 한 번에 배달이나 수거를 못 하면 창고에 돌아온 뒤 다음번에 다시같은 장소로 이동한다.
• 이동하는 길 중간에 다른 집을 방문 할 수 있다
• nlogn 이하의 로직

 

주의할 점

첫 번째로 배달/수거를 시작해야하는 집은 n이 아닐수도 있다.

 

풀이

• 배열을 거꾸로 순회하며 배달을 해야하는 가장 먼 집/ 수거를 해야하는 가장 먼 집을 찾는다.
• 위의 둘 중 더 먼 집이 첫번째로 방문해야할 집이다. answer += Math.max(배달 집, 수거 집) *2을 한다.
• 배열의 뒤에서부터 cap만큼 각각 delivereis, pickups를 감소한다.
  • 가는 길에 마지막 집에서부터 cap만큼 배달한다.
  • 오는 길에 마지막 집에서부터 cap만큼 수거한다.
  • 각각 다음으로 방문해야할 집까지 pop한다
• 위를 배달과 수거를 모두 할 때까지 반복한다.

 

function solution(cap, n, deliveries, pickups) {
    var answer = 0;
    
    // 첫번째 배달/수거해야할 가장 먼 집 찾기
    while(deliveries[n-1] === 0 && pickups[n-1] === 0) {
        deliveries.pop();
        pickups.pop();
        n--;
    }
    // 모두 배달/수거 할때까지
    while(deliveries.length || pickups.length) {
        answer += Math.max(deliveries.length, pickups.length)*2;
        count('deliver');
        count('pickup');
    }
    
    function count(type) {
        const arr = type === 'deliver' ? deliveries : pickups;
        let count = cap;
        // cap만큼 배달을 한다
        while(arr.length && count) {
            // 현재 집의 배달을 모두 할 수 있다
            if (arr[arr.length-1] <= count) {
                count -= arr[arr.length-1];
                arr.pop();
            } 
            // 현재 집의 배달을 모두 할 수는 없다.
            else {
                arr[arr.length-1] -= count;
                count = 0;
            }
        }
        while(arr[arr.length-1] === 0) {
            arr.pop();
        }
    }
    return answer;
}

 

 

느낀점

• 처음에는 문제를 읽고 어렵게 느껴졌지만 차근차근 생각해보니 풀 수 있었다
• 푸는데 시간이 오래 걸렸지만 내 방식대로 풀수 있어서 좋았다.

 

배운점

• 뒤에서부터 배열 순회
• 그리디