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

링크

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

프로그래머스

 

 

설명

택배 배달과 수거하기 문제에 대해서 몰라서 여러 방법을 찾아보고 풀게 되었습니다.

 

택배 배달과 수거하기의 거리를 최소화하는 방법은 한번에 갈 때 최대한 멀리에 있는 택배 상자를 최대한 많이 가져오는 것이 좋습니다.

 

이를 해결하기 위해 택배 상자 배달 숫자를 저장하는 스택과 택배 수거 숫자를 저장하는 스택을 따로 저장합니다.

 

반복문을 돌면서 가장 마지막에 있는 (=가장 먼 곳에 있는) 것부터 하나씩 꺼냅니다.

만약에 아직 택배를 더 배달할 수 있는 수용량이 남거나 더 수거할 수 있는 수용량이 남는다면 한번 더 꺼내봅니다.

수용량을 초과한다면 초과분 만큼만 다시 넣어둡니다.

 

택배 상자를 가져온 최대거리와 수거 상자를 가져온 최대거리 중 더 높은 값이

결국 한번 반복할 때마다 최대한 멀리 간 거리가 됩니다.

 

이를 모든 상자를 배달, 수거 할 때까지 수행합니다.

 

감상

문제를 보고 유형을 보고 결정하는 것과 함께 문제의 해결방법은 어떤 것이 좋은 지 고민해보는 것이 필요했습니다. :)

 

풀이

import java.util.*;

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        
        Stack<int[]> dStack = new Stack<>();
        for(int i=0; i<n; i++) {
            if (deliveries[i] == 0) {
                continue;
            }
            dStack.push(new int[]{i+1, deliveries[i]});
        }
        
        Stack<int[]> pStack = new Stack<>();
        for(int i=0; i<n; i++) {
            if (pickups[i] == 0) {
                continue;
            }
            pStack.push(new int[]{i+1, pickups[i]});
        }
        
        while(!dStack.isEmpty() || !pStack.isEmpty()) {
            int dDistance = 0;
            int dCap = cap;
            while(!dStack.isEmpty() && dCap >= 0) {
                int[] delivery = dStack.pop();
                int distance = delivery[0];
                int count = delivery[1];
                dDistance = Math.max(distance, dDistance);
                dCap -= count;
                if (dCap < 0) {
                    dStack.push(new int[]{distance, -dCap});
                }
            }
            
            int pDistance = 0;
            int pCap = cap;
            while(!pStack.isEmpty() && pCap >= 0) {
                int[] pickup = pStack.pop();
                int distance = pickup[0];
                int count = pickup[1];
                pDistance = Math.max(distance, pDistance);
                pCap -= count;
                if (pCap < 0) {
                    pStack.push(new int[]{distance, -pCap});
                }
            }
            
            int maxDistance = Math.max(dDistance, pDistance);
            answer += 2 * maxDistance;
        }
        
        return answer;
    }
}​