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

📙 1. 문제

Link : 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개의 집에 배달 및 수거하는 과정을 나타낸 예시입니다.

배달 및 수거할 재활용 택배 상자 개수

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

집 #1 집 #2 집 #3 집 #4 집 #5 설명
남은 배달/수거 1/0 0/3 3/0 1/4 2/0 물류창고에서 택배 3개를 트럭에 실어 출발합니다.
남은 배달/수거 1/0 0/3 3/0 0/4 0/0 물류창고에서 5번째 집까지 이동하면서(거리 5) 4번째 집에 택배 1개를 배달하고, 5번째 집에 택배 2개를 배달합니다.
남은 배달/수거 1/0 0/3 3/0 0/0 0/0 5번째 집에서 물류창고까지 이동하면서(거리 5) 4번째 집에서 빈 택배 상자 4개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내리고 택배 4개를 트럭에 싣습니다.
남은 배달/수거 0/0 0/3 0/0 0/0 0/0 물류창고에서 3번째 집까지 이동하면서(거리 3) 1번째 집에 택배 1개를 배달하고, 3번째 집에 택배 3개를 배달합니다.
남은 배달/수거 0/0 0/0 0/0 0/0 0/0 3번째 집에서 물류창고까지 이동하면서(거리 3) 2번째 집에서 빈 택배 상자 3개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내립니다.
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
• 트럭의 초기 위치는 물류창고입니다.

 

풀이 1 : 시간초과

function solution(cap, n, deliveries, pickups) {
    var answer = -1;
    let now_cap;
    let sum =0;
    
    while(1){
//         종료 조건 : deliveries의 모든 요소 = 0 && pickups의 모든 요소 = 0
//         cap에서 시작
        if(deliveries.every(delivery=>delivery===0) && pickups.every(pickup=>pickup===0)) break;
        let last_delivery = n-1-deliveries.reverse().findIndex(it=>it>0)
        let last_pickup = n-1-pickups.reverse().findIndex(it=>it>0)
        if(last_delivery===n) last_delivery=0;
        if(last_pickup===n) last_pickup=0;
        console.log(last_delivery,last_pickup)
        pickups.reverse()
        deliveries.reverse()
        let last = Math.max(last_pickup,last_delivery)
        
//         출발
        now_cap=cap;
        for(let i=last;i>=0;i--){
            if(deliveries[i]>0 && now_cap>0){
                let give = Math.min(deliveries[i],now_cap);
                now_cap-=give;
                deliveries[i]-=give;
            }            
            
        }
//          복귀
        now_cap=cap;
        for(let i=last;i>=0;i--){
            if(pickups[i]>0 && now_cap>0){
                let give = Math.min(pickups[i],now_cap)
                now_cap-=give;
                pickups[i]-=give;
            }
        }
        sum+=(last+1)
    }
    return sum*2;
}

• 왔다 갔다 하는 거리를 줄여야 하는 것이기에, 뒤에 거부터 우선 처리하면 된다고 생각하였다. 그래서 출발할 때와 복귀할 때 모두 for문을 i=last;i>0;i--로 하여 뒤에서부터 처리해 주었다. 
• last는 index값이기에, 마지막에 last+1을하여 sum에 더해주었다.
• 왕복이기에 sum*2를 하여 return하였다.

 

 풀이 2 : 시간 단축 but 여전히 시간 초과

function solution(cap, n, deliveries, pickups) {
    var answer = -1;
    let now_cap;
    let sum =0;
    
    while(1){
//         종료 조건 : deliveries의 모든 요소 = 0 && pickups의 모든 요소 = 0
//         cap에서 시작
        let isDeliveryDone=deliveries.every(delivery=>delivery===0)
        let isPickupDone=pickups.every(pickup=>pickup===0)
        if( isDeliveryDone&& isPickupDone) {
            break;
        }
        
        
        let last_delivery=0;
        let last_pickup=0
        for(let i=0;i<n;i++){
            if(deliveries[i]>0) last_delivery=i;
            if(pickups[i]>0) last_pickup=i;
        }
        let last = Math.max(last_pickup,last_delivery)
        
//         출발
        
        if(!isDeliveryDone){
            now_cap=cap;
            for(let i=last;i>=0;i--){
                if(now_cap===0) break;
                if(deliveries[i]>0){
                    let give = Math.min(deliveries[i],now_cap);
                    now_cap-=give;
                    deliveries[i]-=give;
                }            
            }
        }
//          복귀
        if(!isPickupDone){
            now_cap=cap;
            for(let i=last;i>=0;i--){
                if(now_cap===0) break;
                if(pickups[i]>0){

                    let give = Math.min(pickups[i],now_cap)
                    now_cap-=give;
                    pickups[i]-=give;
                }
            }
        }
        sum+=(last+1)
        
    }
    return sum*2;
}

 

• 시간초과를 해결하기 위해 reverse()를 제거하고, for문을 각각 돌려주었고, now_cap===0이라면 break를 하여 for문을 빠져나오도록 해주었다. 그리고 Delivery가 끝났을 경우, Delivery for문을 돌지 않고, Pickup도 동일하게 처리하였다. 그럼에도 시간초과는 여전했다.
• 어디에서 더 단축시켜주어야 할까.. 도저히 모르겠어서 다른 사람 코드를 참고하였다.

풀이 3 : 다른 사람의 풀이

• 링크

 

function solution(cap, n, deliveries, pickups) {
    let answer = 0;
    let delSum = deliveries.reduce((a,b)=>a+b,0);
    let pickSum = pickups.reduce((a,b)=>a+b,0);
//배달해야하는 화물, 수거해야할 화물 모두 0이되면 종료
    while(delSum !== 0 || pickSum !== 0){
        deleteZero(deliveries);
        deleteZero(pickups);
        let len = Math.max(deliveries.length, pickups.length);
        answer += len*2;
        delSum -= delItem(deliveries, cap);
        pickSum -= delItem(pickups, cap);
    }
    return answer;
}
//뒤에서 부터 0이 있으면 제거해줌
const deleteZero = (arr)=>{
    for(let i=arr.length-1; i>=0; i--){
        if(arr[i] === 0) arr.pop();
        else return;
    }
}
//현재 cap에 맞게, 뒤에서부터 빼줌
//ex) 0 3 2에 cap이 3이면 => 0 2 0
const delItem = (arr,cap) =>{
    let cnt = 0;
    for(let i=arr.length-1; i>=0; i--){
        if(arr[i] >= cap){
            arr[i] -= cap;
            cnt += cap;
            break;
        } 
        else{
            cap -= arr[i];
            cnt += arr[i];
            arr[i] = 0;
        } 
    }
    return cnt;
}

• 내 풀이와의 차이점은, 배열을 그대로 두지 않고, deleteZero메서드를 이용하여 0인 요소는 그때그때 pop을 시켜주었다. 그래서 위의 내 코드처럼 배열의 처음부터 끝까지 모든 요소를 검사하는 불상사는 피할 수 있었다.
• 이미 탐색한, 이미 끝난 요소들은 pop을 시켜 배열의 크기를 줄인다라. 이 풀이가 내 풀이보다 좀 더 직관적인 풀이라 생각한다. 거기다가 시간초과도 해결이 되고 말이다.

---

🤔 2. 느낀 점

처음에 문제를 마주했을 때는 막막했다. "역시 카카오는 어렵네.."라는 두려움이 엄습해 왔다. 그러나 차근차근 그림을 그리며 '해결법'을 생각해 보니 생각했던 것보다 매우 단순한 문제였다.

마지막에 시간초과 때문에 테스트 통과를 전부 하지는 못하였지만, 약간 다른 방식으로 접근한다면 충분히 혼자 힘으로 풀 수 있는 문제였다. '나도 이제는 카카오 코딩테스트도 풀 수 있구나'는 자신감을 얻었다.

이 정도의 난이도가 Lv2의 정답률 28% 문제구나. 앞으로 Lv2의 정답률 25% 이상인 문제들이라면 도전을 해봐야겠다. 그러고 나서 실력이 더 크면 점차 Lv3도 도전을 해봐야지.

 

🤩 3. 한 번 더 짚고 갈 점

탐색을 다 했다 or 이제 볼 일이 없는 요소이다 => pop 시켜서 배열을 단축시키자.