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

 

알고리즘 스프린트 1일차 - [프로그래머스] Lv 2. 택배배달과 수거하기 (카카오 기출)

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

프로그래머스

소요시간

1시간 20분 (디버깅만 30분..)

 

계획

계획 대충 짠게 너무 심하다..

• 완전 구현 문제 였는데 세세한 부분까지 더 계획하지 못했기에 디버깅 시간이 많이 소요되었음
• 오랜만에 알고리즘 풀었더니 계획짜기도 쉽지 않네

풀이

• 자료구조는 크게 신경쓰지 않았고, 딜리버리와 픽업 배열의 끝에서 부터 cap 만큼 제거해 나가는 식으로 풀었다
• 픽업 배열의 가장 끝지점 인덱스와 딜리버리 배열의 가장 끝지점 인덱스를 비교
  • 더 큰 쪽을 answer에 2배하여 추가
• 딜리버리와 픽업의 잔량을 따로 계산하여서 잔량이 0이 될때까지 반복
  • 시간초과 안날거라고 예상했음
    • 반복의 시작지점을 값이 남아있는 가장 먼 인덱스부터 시작하기 때문에
    • 워스트 케이스에서 50 * 10만번 안으로 돌아간다고 예상함
    • 가장 오래걸린 케이스가 15ms 인것을 보면 150만번 정도 돌아가는 케이스가 워스트 케이스인것 같음

결과

코드

function solution(cap, n, deliveries, pickups) {
    var answer = 0;
    let total_d = 0;
    let total_p = 0;
    let end_d = n-1;
    let end_p = n-1;
    for(let i = 0; i < n; i++){
        if (deliveries[i] != 0){
            end_d = i;
            total_d += deliveries[i];
        }  
    }
    
    for(let i = 0; i < n; i++){
        if (pickups[i] != 0){
            end_p = i;
            total_p += pickups[i];
        }  
    }
    while(total_d > 0 || total_p > 0){
        answer += end_d > end_p ? (end_d+1)*2 : (end_p+1)*2;
        let idx_d = end_d;
        let cap_d;
        if(total_d < cap){
            cap_d = total_d;
            total_d = 0;
        }
        else{
            cap_d = cap;
            total_d -= cap;
        }
        while(cap_d >= 0 && idx_d >= 0){
                if (cap_d >= deliveries[idx_d]){
                    cap_d -= deliveries[idx_d];
                    deliveries[idx_d] = 0;
                    idx_d--;
                }
                else{
                    deliveries[idx_d] -= cap_d;
                    cap_d = 0;
                    break;
                }
            
        }
        end_d = idx_d;
        
        let idx_p = end_p;
        let cap_p = cap;
        total_p -= cap;
        while(cap_p >= 0 && idx_p >= 0){
                if (cap_p >= pickups[idx_p]){
                    cap_p -= pickups[idx_p];
                    pickups[idx_p] = 0;
                    idx_p--;
                }
                else{
                    pickups[idx_p] -= cap_p;
                    cap_p = 0;
                    break;  
                }
        }
        end_p = idx_p;
    }    
    
    return answer;
}

 

마치며

오랜만에 알고리즘 다시 시작하려고 하니 감잡기가 쉽지않다.

코드 작성 전에 더 정확한 계획을 짜고 코드 작성할 것!!!!