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

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

 

 

---

접근 방법

매 순간 최적의 선택을 통해 문제를 해결해 나가는 그리디 유형이다.

먼 곳의 택배의 갯수를 매번 최적으로 가져오면 최소한의 이동거리를 얻을 수 있다.

멀리 있는 지점부터 시작해 트럭의 용량만큼 배달하고, 용량이 허용하는 한 수거작업 또한 진행한다.

 

 

import java.util.*;
class Solution {
    public int update(int pointer, int[] arr, int cap){
        int sum = 0;
        while(pointer >= 0 && sum < cap){
            sum += arr[pointer];
            arr[pointer--] = 0;
        }

        if(sum > cap){
            arr[++pointer] =  sum - cap;
        }
        
        return pointer;
    }
    //탐욕법
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        int dPointer = n-1;
        int pPointer = n-1;

        while(dPointer >= 0 || pPointer >= 0){
            while(dPointer >= 0 && deliveries[dPointer] == 0) dPointer--;
            while(pPointer >= 0 && pickups[pPointer] == 0) pPointer--;
            answer += (Math.max(dPointer, pPointer)+1)*2;
            dPointer = update(dPointer, deliveries, cap);
            pPointer = update(pPointer, pickups, cap);
        }
      
        return answer;
    }
}