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

난이도 : Level 2
알고리즘 유형 : 그리드
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/150369

 

 

문제 풀이

• 메인 생각 : 가장 먼 거리에 있는 집 부터 최대 용량으로 배달 및 수거하기.

택배를 배달 및 수거하면서 최소로 이동하려면 한 번 나갈 때 최대한의 택배를 배달/수거해야 한다.

또한 제일 멀리있는 집 부터 택배를 배달/수거해야지 최소 거리로 이동할 수 있다.

 

택배를 전달하기 위해서 앞에서부터 순차적으로 전달 또는 뒤에서 부터 순차적으로 전달하는 방법을 떠올릴 수 있다.

 

이때 최대한의 택배를 앞에서부터 전달하는 경우 뒤에서부터 전달할 때보다 더 많이 이동할 수 있다.

 

예를 들어 cap이 4이고 delivery가 [0, 1, 2, 0, 4]이며, 수거해야할 택배는 없다고 가정하자.

 

앞에서 부터 전달

최대한의 짐을 가지고 전달할 것이므로 위 경우,
처음에 2번째 집의 택배 1개, 3번재 집의 택배 2개, 5번째 집의 택배 1개를 들고 배달하여 총 10 이동할 것이다. (왕복이므로)

그 뒤에 남은 5번째 집의 택배 3개를 배달하여 추가적으로 10 을 이동하여 20을 정답이라고 출력할 것이다.

 

하지만 실제 정답은 16이므로 틀리게 된다.

 

반대로 뒤에서 부터 전달하는 경우 제일 먼 거리를 결국에 이동해야함으로 제일 멀리 이동할 때 최대한의 택배를 들고감으로 불필요하게 이동하는 일이 없게 된다.

 

그럼 이제 수거 및 배달용 집 중 제일 멀리 있는 집을 선택하면서 이동거리를 합해주면 정답을 구할 수 있다.

 

제일 멀리 있는 집을 찾기 위해, 배달용 집 중 가장 멀리 있는 집을 dIdx, 수거용 집 중 가장 멀리있는 집을 pIdx라고 하겠다.

먼저 dIdx와 pIdx 둘다 n - 1로 초기화 한다.

 

이후 dIdx와 pIdx 가 0보다 클 동안 while문을 실행할 것이다.

dIdx와 pIdx에 있는 집에 배달/수거할 택배가 없을 수 있으므로 각 인덱스의 집에 배달/수거할 택배가 있을 때까지 1씩 빼준다.

그럼 각각 배달용 및 수거용 제일 먼 집을 구할 수 있다.

그러면 인덱스가 0부터 시작함으로 1 더해주고, 왕복으로 갔다옴 2 곱하여 이동한 거리에 더한다.

// 2 * Math.max(dIdx + 1, pIdx + 1)

 

이후 최대 용량만큼 배달/수거했음으로 뒤에서 부터 용량 만큼 빼주면서 dIdx와 pIdx를 빼주면 된다.

 

function solution(cap, n, deliveries, pickups) {
    let answer = 0;
    
    let [dIdx, pIdx] = [n - 1, n - 1];
    
    while(dIdx >= 0 || pIdx >= 0) {
        while(dIdx >= 0 && deliveries[dIdx] === 0) dIdx--;
        while(pIdx >= 0 && pickups[pIdx] === 0) pIdx--;
        
        answer += 2 * Math.max(dIdx + 1, pIdx + 1);
        
        let [dCap, pCap] = [cap, cap];
        
        while(dCap > 0 && dIdx >= 0) {
            if(deliveries[dIdx] > 0) { deliveries[dIdx]--; dCap--; }
            else dIdx--;
        }
        while(pCap > 0 && pIdx >= 0) {
            if(pickups[pIdx] > 0) { pickups[pIdx]--; pCap--; }
            else pIdx--;
        }
    }
    
    return answer;
}

 

 

회고

최근에 PCCP를 쳤는데 생각보다 실력이 저조했다..
이유를 생각해보니 이때까지 출력 예외 상황 및 문장을 제대로 읽지 않거나 로직 상의 문제로 한 번에 통과하지 못 한 경우가 종종 있었다.

이때까지는 문제를 많이 풀었으니 당연히 잘한다고 생각했지만 정답인지 알려주지 않는 문제에서 내 코드가 틀리지 않다는 보장이 없다..
그리고 그에 대한 검증도 없었다.

 

그래서 앞으로는 문제를 꼼꼼히 읽으면서, 입력, 출력 예시 및 예외 작성 및 로직을 요약해놓고, 로직의 시간복잡도를 계산해본 다음에 실제로 구현하며, 테스트케이스도 작성해봐야겠다!

 

입력, 출력 및 로직 작성 과 시간복잡도 계산은 하고 있던 일이라서 어렵지 않지만.. 테스트 케이스를 엣지 케이스에 대한 테스트 케이스 작성이 약간 까다로울 것 같다..

힘내보자!!!!