Level 2️⃣ - 택배 배달과 수거하기(2023 KAKAO BLIND RECRUITMENT)

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

프로그래머스

 

 

문제 접근하기

핵심 요구사항은 "최소 이동 거리"이다.

예시를 분석하면서 문제를 이해하는 것이 매우 중요하다.

 

1. 먼저 배달을 할 때는 가장 멀리 있는 곳부터 배달을 완료해야한다.

그렇지 않으면 또 다시 먼 거리를 이동해야하기 때문에 "최소 이동 거리"를 구하기에는 비효율적이기 때문이다.

그런데 고려해야할 부분이 하나 더 있다. 바로 빈 상자를 픽업해야한다는 것이다.

 

예를 들어 다음과 같이 입력값이 주어진다고 가정해보자.

deliveries : [1, 0, 3, 0, 0]

pickups : [0, 3, 0, 4, 0]

배달은 3번째 집까지 배달을 하면 되지만 픽업은 4번째 집에서부터 픽업을 해야한다.

여기서 효율적인 방법은 4번째 집까지 배달을 가고 돌아오면서 상자를 픽업하는 것이 가장 효율적인 방법이다.

 

반대로 입력값이 다음과 같다고 가정해보자.

deliveries : [1, 0, 3, 0, 5]

pickups : [0, 1, 2, 0, 0]

이 경우에는 5번째 집까지 배달을 갔다가 돌아오면서 3번째 집부터 상자를 픽업하는 것이 가장 효율적인 방법이다.

 

2. 그렇다면 "최소 이동 거리"를 구하기 위해서 한번 배달할 때 이동해야하는 거리는 deliveries 배열에서 마지막으로 0이 아닌 숫자가 있는 곳과 pickups 배열에서 마지막으로 0이 아닌 숫자가 있는 곳 중 최댓값을 이동해야 가장 효율적인 이동 거리가 된다는 것이다.

 

위의 두 가지 고려사항을 염두하고 문제를 설계했다.

설계

1. deliveries와 pickups 배열 중 0이 아닌 숫자가 마지막으로 등장하는 위치를 구해 최댓값 m을 구한다.

  - 이때 위치는 인덱스값이다.

2. ret에 (m+1)*2 를 더한다. 왜냐하면 m은 인덱스의 값이고 왕복값이기 때문에 2를 곱해주어야한다.

3. delivieries 배열 중 cap을 고려해서 뒤에서부터 배달을 진행한다.

// 의사 코드
for let i = m; i >= 0, i--
  // 택배 배달이 가능하다면
  if(capacity >= deliveries[i]){
    capacity -= deliveries[i];
    deliveries[i] = 0
  }
  // 택배 배달이 불가능하다면 Loop문을 빠져나온다.
  else {
    deliveries[i] -= capacity;
    break;
  }

4. pickups 배열 중 cap을 고려해서 뒤에서부터 픽업한다. 로직은 위의 의사코드와 동일하다.

구현

function solution(cap, n, deliveries, pickups) {
    let prev = deliveries.length - 1;
    let ret = 0;
    while(true){
        // 1. delivers와 pickups 배열 중, 0이 아닌 숫자가 마지막으로 등장하는 길이만큼을 구한다.
        let pointA = -1;
        let pointB = -1;
        for(let i = prev; i >= 0; i--){
            if(deliveries[i] !== 0) {
                pointA = i;
                break;
            }
        }
        for(let i = prev; i >= 0; i--){
            if(pickups[i] !== 0) {
                pointB = i;
                break;
            }
        }
        if(pointA === -1 && pointB === -1) break;
        let m = Math.max(pointA, pointB);
        prev = m;
        ret += (m + 1) * 2;
        // 2. 뒤에서부터 cap 용량만큼 택배 배달을 한다.
        let capacity = cap;
        for(let i = m; i >= 0; i--){
            if(capacity >= deliveries[i]) {
                capacity -= deliveries[i];
                deliveries[i] = 0;
            }
            else {
                deliveries[i] -= capacity;
                break;
            }
        }
        capacity = cap;
        for(let i = m; i >= 0; i--){
            if(capacity >= pickups[i]){
                capacity -= pickups[i];
                pickups[i] = 0;
            }
            else {
                pickups[i] -= capacity;
                break;
            }
        }
    }
    return ret;
}

 

❌하지만 하나의 테스트 케이스를 통과하지 못했다.

구현 수정

0이 아닌 숫자의 마지막 위치를 찾을 때 Loop문을 이용해서 찾는 것이 아니라 deliverLast와 pickupLast라는 변수를 이용해서 이전의 마지막 위치를 저장할 수 있게끔 구현을 수정했다.

이렇게 하면 정확하게 0이 아닌 숫자의 마지막 위치에서 배달 및 픽업을 진행할 수 있기 때문에 불필요한 연산을 줄일 수가 있다.

 

이전 코드와 큰 차이가 있을까 싶었지만 4900ms에서 13ms까지 시간이 단축된 것을 확인했다.

function solution(cap, n, deliveries, pickups) {
    let ret = 0;
    let deliverLast = deliveries.length - 1;
    let pickupLast = pickups.length - 1;
    
    while (true) {
        // 0이 아닌 숫자의 마지막 위치 찾기
        while (deliverLast >= 0 && deliveries[deliverLast] === 0) deliverLast--;
        while (pickupLast >= 0 && pickups[pickupLast] === 0) pickupLast--;
        
        if (deliverLast === -1 && pickupLast === -1) break;
        
        // 최대로 이동해야 하는 위치
        let m = Math.max(deliverLast, pickupLast);
        ret += (m + 1) * 2;
        
        // 택배 배달
        let capacity = cap;
        for (let i = deliverLast; i >= 0; i--) {
            if (deliveries[i] <= capacity) {
                capacity -= deliveries[i];
                deliveries[i] = 0;
            } else {
                deliveries[i] -= capacity;
                break;
            }
        }
        
        // 택배 픽업
        capacity = cap;
        for (let i = pickupLast; i >= 0; i--) {
            if (pickups[i] <= capacity) {
                capacity -= pickups[i];
                pickups[i] = 0;
            } else {
                pickups[i] -= capacity;
                break;
            }
        }
    }
    return ret;
}