프로그래머스 - 택배 배달과 수거하기

문제

https://www.acmicpc.net/problem/150369

풀이

• 최적의 경로는 가장 멀리 있는 곳에 배달 혹은 수거를 우선으로 해야 한다.
• 어차피 모든 배달과 수거를 해야한다는 것은 방문을 하게 된다는 것이므로 최대한 멀리 있는 것의 배달과 수거를 끝내야 그 뒤의 배달과 수거를 더 짧은 이동거리로 수행할 수 있다.
• 배열의 끝에서부터 참조하여 다음의 배달(혹은 수행) 중 가장 멀리 있는 곳의 위치를 구한다.
• 배달과 수거 중 더 멀리 있는 곳을 기준으로 +1 을하고 *2 (왕복) 한 값을 더해준다.

유의할 점

• index를 다루는 문제는 항상 범위를 고려해야 한다.
• 예를 들어 아래 코드에서도 idx1>=0 의 위치가 바뀌면 런타임 에러가 난다.

     while(idx1>=0 && deliveries[idx1]==0 ) idx1--;

코드

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        
        long answer=0; 
        int idx1 = n-1; 
        int idx2 = n-1 ;
        
        while(idx1>=0 && deliveries[idx1]==0 ) idx1--;
        while(idx2>=0 && pickups[idx2]==0) idx2--; 
        

        while(idx1>=0 || idx2>=0){
            answer += (Math.max(idx1,idx2)+1)*2; 
            int cur = cap ; 

            while(cur>0 && idx1>=0){
                if(deliveries[idx1]>cur){
                    deliveries[idx1]-= cur; 
                    cur = 0; 
                }else{
                    cur-= deliveries[idx1]; 
                    deliveries[idx1]=0; 
                    while(idx1>=0 && deliveries[idx1]==0) idx1--; 
                }
            }
            
            cur = cap ; 
            while(cur>0&& idx2>=0){
                if(pickups[idx2]>cur){
                    pickups[idx2]-= cur; 
                    cur = 0; 
                }else{
                    cur-= pickups[idx2]; 
                    pickups[idx2]=0; 
                    while(idx2>=0 && pickups[idx2]==0) idx2--; 
                }
            }
        }
     return answer; 
    }
}