프로그래머스 Level2 택배 배달과 수거하기 (Java)

• https://school.programmers.co.kr/learn/courses/30/lessons/150369
• 문제
  • n개의 집에 택배를 배달한다. 빈 택배 또한 수거한다.
  • 각 i번째 집은 물류창고로부터 i만큼 떨어져 있다. 또한 j번째 집과는 j-i만큼 떨어져 있다.(1 ≤ i ≤ j ≤ n)
  • 트럭은 한번에 cap개의 택배상자를 실을 수 있다.
  • 각 집에 배달 및 수거할 때, 원하는 갯수만큼 택배를 배달 및 수거할 수 있다.
  • 트럭의 최소 이동 거리를 반환하시오.
  • (예시는 사이트 참고)
• 제한사항
  • 1 ≤ cap ≤ 50
  • 1 ≤ n ≤ 100,000
  • deliveries의 길이 = pickups의 길이 = n
    • deliveries[i]는 i+1번째 집에 배달할 재활용 택배 상자의 개수를 나타냅니다.
    • pickups[i]는 i+1번째 집에서 수거할 빈 재활용 택배 상자의 개수를 나타냅니다.
    • 0 ≤ deliveries의 원소 ≤ 50
    • 0 ≤ pickups의 원소 ≤ 50
  • 트럭의 초기 위치는 물류창고입니다.
• 코드

import java.util.Stack;

public class Solution {
    public long solution(int cap, int n, int[] deliveries, int[] pickups) {
        long answer = 0;
        Stack<Integer> dStack = new Stack<>();
        Stack<Integer> pStack = new Stack<>();
        for(int i = 0; i < n; i++) {
        	if(deliveries[i] > 0) {
        		dStack.add(i);
        	}
        	if(pickups[i] > 0) {
        		pStack.add(i);
        	}
        }
        
        
        
        while(!dStack.empty() && !pStack.empty()) {
        	answer += Math.max((dStack.peek()+1)*2, (pStack.peek()+1)*2);
        	
        	int box = 0;
        	while(!dStack.empty() && box <= cap) {
        		if(deliveries[dStack.peek()]+box <= cap) {
        			box += deliveries[dStack.peek()];
        		}else {
        			deliveries[dStack.peek()] -= (cap-box);
        			break;
        		}
        		dStack.pop();
        	}
        	
        	box = 0;
        	while(!pStack.empty() && box <= cap) {
        		if(pickups[pStack.peek()]+box <= cap) {
        			box += pickups[pStack.peek()];
        		}else {
        			pickups[pStack.peek()] -= (cap-box);
        			break;
        		}
        		pStack.pop();
        	}
        }
        
        while(!dStack.empty()) {
        	answer += (dStack.peek()+1)*2;
        	
        	int box = 0;
        	while(!dStack.empty() && box <= cap) {
        		if(deliveries[dStack.peek()]+box <= cap) {
        			box += deliveries[dStack.peek()];
        		}else {
        			deliveries[dStack.peek()] -= (cap-box);
        			break;
        		}
        		dStack.pop();
        	}
        }
        
        while(!pStack.empty()) {
        	answer += (pStack.peek()+1)*2;
        	
        	int box = 0;
        	while(!pStack.empty() && box <= cap) {
        		if(pickups[pStack.peek()]+box <= cap) {
        			box += pickups[pStack.peek()];
        		}else {
        			pickups[pStack.peek()] -= (cap-box);
        			break;
        		}
        		pStack.pop();
        	}
        }
        return answer;
    }
}

• 풀이
  • 2023 KAKAO BLIND RECRUITMENT 문제로, Greedy로 풀 수 있는 문제였다.크게 두가지로 나눠서 생각해보면 Greedy라는 것을 알 수 있다.
    1. 배달할 집의 거리가 수거할 집의 거리보다 긴 경우
    2. 수거할 집의 거리가 배달할 집의 거리보다 긴 경우
  • 아래와 같은 과정을 거치기 때문에 두가지 경우 모두 똑같다는 것을 알 수 있다.
    1. 더 먼집까지 가면서 택배를 배달한다.
    2. 물류창고로 복귀하면서 택배를 수거한다.
  • 즉 배달과 수거 모두 어차피 먼 집까지 갔다가 오는 과정에서 모두 해결이 가능하다.
  • 이 문제에서 주의할 점은 deliveries의 스택과 pickups의 스택을 동시에 운영하면서 둘 중 하나가 empty상태가 되었을 때 런타임 에러가 걸릴 수 있다. 구현하면서 이 점을 주의해야 한다.