택배 배달과 수거하기 (Programmers Lv.2)

문제

...
이때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 return 하도록 solution 함수를 완성해 주세요.

https://school.programmers.co.kr/learn/courses/30/lessons/150369?language=cpp

프로그래머스

 

풀이

해당 문제는 2023 KAKAO BLIND RECRUITMENT에 출제되었고, 문제에 도전한 후 봤던 참고 풀이가 내가 접근한 방식과 다르게 간단하고 명확해서 다시 다뤄볼 필요가 있을 것 같아 들고와봤다.

 

먼저 내가 풀어본 풀이를 살펴보자.

 

C++)

#include <string>
#include <vector>

using namespace std;

int Cap = 0;
int lastIdx = 0;

bool findLast(vector<int> &deliveries, vector<int> &pickups) {
    for(int i = deliveries.size() - 1; i >= 0 ; i--) {
        if(deliveries[i] != 0 || pickups[i] != 0) {
            lastIdx = i;
            return true;
        }
    }
    
    return false;
}

void deliver(vector<int> &deliveries, vector<int> &pickups) {
    int deliverBox = Cap;
    int pickupBox = 0;
    
    for(int i = lastIdx; i >= 0; i--) {
        if(deliverBox == 0 && pickupBox == Cap)
            return;
        
        if(deliveries[i] != 0 && deliverBox != 0) {
            if(deliveries[i] <= deliverBox) {
                deliverBox -= deliveries[i];
                deliveries[i] = 0;
            } else {
                deliveries[i] -= deliverBox;
                deliverBox = 0;
            }
        }
        
        if(pickups[i] != 0 && pickupBox != Cap) {
            if(pickupBox + pickups[i] <= Cap) {
                pickupBox += pickups[i];
                pickups[i] = 0;
            } else {
                pickups[i] -= (Cap - pickupBox);
                pickupBox = Cap;
            } 
        }
    }
}

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    long long answer = 0;
    Cap = cap;
    
    while(findLast(deliveries, pickups)) {
        deliver(deliveries, pickups);
        answer += 2 * (lastIdx + 1);
    }
    
    return answer;
}

 

아쉽지만 테케 2개가 나가버려 90점을 받은 풀이다. 문제를 풀면서도 시간 초과가 걱정되었는데, 아니나 다를까 바로 시간이 초과되어 버렸다... 우선적으로 내가 접근한 방식은 deliveries 와 pickups 에서 배열의 마지막부터 시작하여 재활용박스가 남아있는 인덱스를 찾아 로직을 풀어가는 풀이였다. 그런데 그 인덱스를 찾는 방식이 매번 n 만큼 탐색을 해야하고, 거기에 lastIdx  까지 루프를 돌리니 n 값이 커지면 시간초과가 날 수 밖에 없다는...

 

따라서 다른 풀이로 접근할 필요가 있었고, 많은 고민 끝에 그리디를 이용하는 풀이가 가장 적합하다는 판단을 내렸다.

 

C++)

#include <string>
#include <vector>

using namespace std;

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    long long answer = 0;
    
    // 배달 박스, 수거 박스
    long long deliverBox = 0;
    long long pickupBox = 0;
    
    for(int i = n - 1; i >= 0; i--) {
        deliverBox -= deliveries[i];
        pickupBox -= pickups[i];
        
        // 횟수
        int cnt = 0;
        while(deliverBox < 0 || pickupBox < 0) {
            // 배달, 수거 완료될 때까지 횟수 증가
            deliverBox += cap;
            pickupBox += cap;
            
            cnt++;
        }
        
        // 왕복
        answer += (i + 1) * cnt * 2;
    }
    
    return answer;
}

 

보다시피 풀이가 너무 간단해진다. 알고리즘을 풀 때는 처음에 방향성을 잘 잡아야 올바른? 깔끔한? 접근이 가능하다는 것을 새삼 깨닫는다. 그래서 문제를 보자마자 풀지말고, 풀이 방법을 고민한 후 풀라는 팁이 있는 거 겠지...

 

그럼, 이제 내가 현재 공부하고 있는 Javascript로 풀어보자.

 

JS)

function solution(cap, n, deliveries, pickups) {
    let answer = 0;
    
    let deliveryBox = 0, pickupBox = 0;
    for(let i = n - 1; i >= 0; i--) {
        deliveryBox -= deliveries[i];
        pickupBox -= pickups[i];
        
        let cnt = 0;
        while(deliveryBox < 0 || pickupBox < 0) {
            deliveryBox += cap;
            pickupBox += cap;
            
            cnt++;
        }
        
        // 왕복
        answer += (i + 1) * cnt * 2;
    }
    
    return answer;
}

 

매번 느끼지만 C++로 풀고 JS풀이로 옮기면, 새삼스레 JS의 위대함을 느낀다... 너무 간편해... 마치 이전에 파이썬을 처음 접했을 때 같달까...