[2023 KAKAO BLIND RECRUITMENT] 택배 배달과 수거하기

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

[이 문제는 프로그래머스에서 푼 문제입니다.]
이 문제는 그리디 알고리즘과 스택을 이용하여 풀 수 있습니다. 그리디 알고리즘이란 각 단계에서 가장 최선의 선택을 하는 기법으로, 이 문제의 경우 정답을 도출하기 위해선 크게 3가지만 고려하면 됩니다.

1. 가장 먼 집부터 작업 진행
2. 갈 때는 최대 적재량으로 출발
3. 올 때는 최대 적재량으로 짐 싣고 오기

즉 쉽게 말해, 무조건 먼 쪽의 집에서부터 작업을 진행하면 되고, 실행 시 최대 적재량을 가득 채운 상태로 작업을 진행하면 최단 거리를 구할 수 있습니다. 이를 구현하기 위해 만약 완전탐색으로 진행하게 된다면 배달과 수거를 진행할 집을 탐색하고 그 내부에서 현재 집에서 싣을 수 있는 택배 수를 넘었는지 여부를 따져가며 다시 반복문을 돌아 탐색하게 되는데 이 경우 시간 초과가 발생하게 됩니다. 이를 해결하기 위해 가장 먼 집을 가장 먼저 진행하기 때문에 스택을 사용하여 집 주소를 탐색하면 배달과 수거를 진행할 집을 탐색하는 소요가 없어지고 스택의 peek값으로 쉽게 찾을 수 있기 때문에 시간 복잡도가 감소합니다.

다음은 코드입니다.

import java.util.*;

class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        
        // 그리디
        // 1. 가장 먼 집부터 작업 진행
        // 2. 갈 때는 최대 적재량으로 출발
        // 3. 올 때는 최대 적재량으로 짐 싣고 오기
        
        // 택배 배달, 박스 수거 각각 스택 생성
        Stack<Integer> deliveriesStack = new Stack<>();
        Stack<Integer> pickupsStack = new Stack<>();
        
        // 택배 배달, 박수 수거 각각 0이 아닌 값들을 앞에서 순서대로 스택에 추가
        // 그렇게 되면 스택에서 값을 뽑을 때 가장 마지막 집이 선택
        for(int i=0;i<n;i++){
            if(deliveries[i]!=0) deliveriesStack.push(i);
            if(pickups[i]!=0) pickupsStack.push(i);
        }
        
        // 왕복해서 갈 때는 배달, 올 때는 수거를 진행하므로
        // 배달 스택과 수거 스택의 peek()를 비교하여 더 큰 수의 *2 만큼 answer 더하기
        while(!deliveriesStack.isEmpty() || !pickupsStack.isEmpty()){
            // 만약 두 스택 중 하나가 다 비었다면 무조건 남은 친구를 뽑고 그 수의 *2 만큼 answer 더하기
            
            // 1. 배달 스택이 비었을 경우 : 수거 스택만 뽑은 후 그 수의 *2 만큼 더하기
            if(deliveriesStack.isEmpty() && !pickupsStack.isEmpty()){
                int adder = getAdder(pickupsStack,cap,pickups);
                answer += (adder+1)*2;
                
                // 택배 
            }
            // 2. 수거 스택이 비었을 경우 : 배달 스택만 뽑은 후 그 수의 *2 만큼 더하기
            else if(!deliveriesStack.isEmpty() && pickupsStack.isEmpty()){
                int adder = getAdder(deliveriesStack,cap,deliveries);
                answer += (adder+1)*2;
            }
            // 3. 둘 다 비어있지 않을 경우 : 더 큰 수의 *2 만큼 더하기
            else{
                int deliveriesPeek = getAdder(deliveriesStack,cap,deliveries);
                int pickupsPeek = getAdder(pickupsStack,cap,pickups);
                int adder = Math.max(deliveriesPeek, pickupsPeek);
                answer += (adder+1)*2;
            }
            
        }
        
        return answer;
    }
    
    static int getAdder(Stack<Integer> stack, int cap, int[] arr){
        int currCap = 0;
        int adder = 0;
        while(cap > currCap){
            // 만약 스택이 비었다면 종료
            if(stack.isEmpty()) break;
            
            int peek = stack.peek();
            adder = Math.max(adder,peek);

            // 만약 현재 집에서 싣을 수 있는 택배 수를 넘었을 경우
            if(arr[peek] + currCap > cap){
                // 차이만큼 더하고 pop 하지 않고 deliveries[] 값을 차이만큼 뺀다
                int diff = cap - currCap;
                arr[peek] -= diff;
                currCap = cap;
            }

            // 만약 현재 집에서 싣을 수 있는 택배 수를 넘지 않았을 경우
            else{
                // currCap에 해당값 그대로 더하고 pop
                currCap += arr[peek];
                stack.pop();
            }

        }
        return adder;
    }
}