[프로그래머스/level2/JS] 택배 배달과 수거하기(2023 Kakao Blind Recruitment)

문제 링크

2023 Kakao Blind Recruitment 택배 배달과 수거하기

 

문제 풀이

2023년 카카오 블라인드 채용 택배 배달과 수거하기 문제이다. 택배를 배달하고 수거하는데 걸리는 최소 이동 거리를 계산하는 문제이다. 문제를 읽자마자 바로 방법이 떠오르지는 않았고 곰곰이 생각해보니 쉽게 방법을 떠올릴 수 있었다.

 

가는 길에는 배달만하고 오는 길에만 수거만 하도록 하자. 만약 가는 길에 배달도 하고 수거도 같이 하게되면 배달할 때 수거할 양도 생각해야하고 만약 중간에 수거를 해서 용량이 차버렸다면 다시 트럭을 비우고 먼 곳까지 다시 와야하는 불상사가 일어난다.

 

그렇다면 문제가 조금 쉬워졌다. 갈때는 배달만하고 올때는 수거만 한다. 그러면 어떻게 거리를 최소화 할 수 있을까?

어차피 택배를 배달하거나 수거하려면 항상 해당 지점을 방문해야 한다. 그렇다면 먼 곳의 택배들부터 배달하고 수거하면 항상 최적화된 횟수를 얻을 수 있지 않을까? 그렇다 이 문제는 Greedy 문제였다.

 

배달과 수거 과정은 별개으로 생각하고 배달 나온 김에 수거를 한다고 생각하자. 그렇다면 배달해야하는 제일 먼 집 거리와 수거해야하는 먼 집 거리가 있을 때 둘 중 큰 거리를 한번 배달 나왔을 때 이동한 거리로 생각하고 왕복이므로 2를 곱해서 더해주면 쉽게 해결할 수 있다.

코드

function solution(cap, n, deliveries, pickups) {
    let answer = 0;
    
    const moveTruck = (map, cap) => {
        let endDistance = 0;
        
        while(map.length && cap) {
        	// 제일 먼 집의 배달 or 수거량
            const count = map[map.length - 1];
            
            // 최초로 배달 or 수거량이 있을 때 값을 저장한다.
            if(!endDistance && count) endDistance = map.length;
            
            if(count <= cap) {
            	// 더 배달 or 수거할 수 있다면 앞집으로 이동한다.
                cap -= count;
                map.pop();
            } else if (count > cap) {
            	// 더 배달 or 수거할 수 없다면 할수 있는 만큼만 처리한다.
                map[map.length - 1] = count - cap;
                break;
            }
        }
        
        // 최초로 배달 or 수거할 택배가 있을 때의 거리
        return endDistance;
    }
    
    while(deliveries.length || pickups.length) {       
        const deliveryDistance = moveTruck(deliveries, cap)
        const pickDistance = moveTruck(pickups, cap)
        
        // 배달, 수거 둘 중 먼 집의 거리로 갈때 올때 생각해서 2배를 하여 더해준다.
        answer += Math.max(deliveryDistance, pickDistance) * 2
    }
    
    return answer;
}

 

 

오류가 있거나 궁금한 부분이 있으면 언제든지 댓글을 달아주세요.

항상 읽어주셔서 감사합니다.