(프로그래머스 KAKAO JS)택배 배달과 수거하기

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

프로그래머스

 

greedy 알고리즘으로 접근.

택배 배달과 수거를 앞에서가 아닌 뒤에서부터 진행을 하면 된다.

deveriesIndex와 pickupsIndex를 선언하여 n - 1로 저장하고, 이 두 변수를 이용해서 더 큰 값이 사실상 출발 위치가 된다.

 

while문을 이용해 두 인덱스가 모든 배열을 순회한 -1 값이 될 때까지 반복한다.

(뒤에서부터 순회했기 때문에 n - 1 ~ 0 으로 간다.)

deliver_cap, pickup_cap은 현재 택배차가 각각 배달/수거 한 개수를 나타낸다.

 

먼저 deliveriesIndex와 pickupsIndex에 위치한 값이 0이 아닐 때까지 - 1 을 해주자.

그렇지 않으면 굳이 안가도 되는 지점부터 시작해야 하기 때문이다.

 

두 while문이 끝나면 answer에는 (두 인덱스 값 중 더 큰 값 + 1) * 2를 해주어 배달과 수거를 한 카운팅을 한다.

카운팅이 끝나면 배달과 수거 작업을 진행한다.

각 for문은 위에서 말했던 것처럼 거꾸로 시작한다.

 

현재 인덱스의 값 + delivery/pickup cap <= cap이라면

배달/수거를  다 할 수 있으며, 0으로 만들 수 있다.

또한, 현재 위치는 시작점이 될 수 없기 때문에 deliveriesIndex--/pickupsIndex-- 한다.

 

그렇지 않고 배달/수거를 할 수 없다면(배달차가 꽉 찬 경우)

최대한 배달/수거를 할 수 있을 만큼 하고, 시작점인 deliveriesIndex/pickupsIndex를 i로 저장하여 break.

 

이 루프를 반복하면 답을 구할 수 있다.

function solution(cap, n, deliveries, pickups) {
    let answer = 0;
    let deliveriesIndex = n - 1;
    let pickupsIndex = n - 1;

    while(deliveriesIndex >= 0 || pickupsIndex >= 0) {
        let deliver_cap = 0;
        let pickup_cap = 0;
        
        while(deliveries[deliveriesIndex] == 0) {
            deliveriesIndex--;
        }
        
        while(pickups[pickupsIndex] == 0) {
            pickupsIndex--;
        }
        
        answer += (Math.max(deliveriesIndex + 1, pickupsIndex + 1)) * 2;
        
        // do best to delivery
        for(let i = deliveriesIndex; i >= 0; i--) {
            if(deliver_cap + deliveries[i] <= cap) {
                deliver_cap += deliveries[i];
                deliveries[i] = 0;
                deliveriesIndex--;
            } else {
                deliveries[i] = deliver_cap + deliveries[i] - cap;
                deliveriesIndex = i;
                break;
            }
        }
        
        // do best to pickup
        for(let i = pickupsIndex; i >= 0; i--) {
            if(pickup_cap + pickups[i] <= cap) {
                pickup_cap += pickups[i];
                pickups[i] = 0;
                pickupsIndex--;
            } else {
                pickups[i] = pickup_cap + pickups[i] - cap;
                pickupsIndex = i;
                break;
            }
        }
    }

    return answer;
}