🔒 문제 설명
당신은 일렬로 나열된
n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.
배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n)
트럭에는 재활용 택배 상자를 최대cap개 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다. 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.
입력
트럭에 실을 수 있는 재활용 택배 상자의 최대 개수를 나타내는 정수
cap, 배달할 집의 개수를 나타내는 정수n, 각 집에 배달할 재활용 택배 상자의 개수를 담은 1차원 정수 배열deliveries와 각 집에서 수거할 빈 재활용 택배 상자의 개수를 담은 1차원 정수 배열pickups가 매개변수로 주어집니다.
출력
트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 return 하도록
solution함수를 완성해 주세요.
조건
- 1 ≤
cap≤ 50- 1 ≤
n≤ 100,000deliveries의 길이 =pickups의 길이 = ndeliveries[i]는 i+1번째 집에 배달할 재활용 택배 상자의 개수를 나타냅니다.pickups[i]는 i+1번째 집에서 수거할 빈 재활용 택배 상자의 개수를 나타냅니다.- 0 ≤
deliveries의 원소 ≤ 50- 0 ≤
pickups의 원소 ≤ 50- 트럭의 초기 위치는 물류창고입니다.
🔑 해결 아이디어
단순 구현에 가까운 문제였다. 배송과 픽업에 대해 따로 가야하는 최대 거리를 기억해 둔 후, 각 운행에 대해 두 거리 중 더 긴 거리로 이동한다. 한번의 운행마다 pickups와 deliveries 배열을 갱신한다.
💻 소스코드
class Solution {
/*
n개의 집, 크기가 같은 재활용 상자
최소 이동거리
*/
/*
배달 순서 :
먼저 배달 다 하고
주울 수 있는게 있으면 줍는다.
그럼, 제일 멀게 가야하는 곳을 계속 갱신하면서 cap의 사정에 맞게 내려주고 돌아오면서 다시 들고온다.
*/
public long solution(int cap, int n, int[] deliveries, int[] pickups) {
//10:03 ~ 10:24 (90점) / ~ 11:19 (10점) / 11:31 (100점)
int deliveryGoal = deliveries.length - 1;
int pickupGoal = pickups.length - 1;
long answer = 0;
while(pickupGoal != 0 || deliveryGoal != 0){
while(deliveryGoal >= 0 && deliveries[deliveryGoal] == 0){
deliveryGoal--;
}
while(pickupGoal >= 0 && pickups[pickupGoal] == 0)
pickupGoal--;
int goal = deliveryGoal > pickupGoal? deliveryGoal : pickupGoal;
if(goal < 0){
//System.out.println("goal is neg");
return answer*2;
}
int deliveryDay = deliveries[goal] / cap;
int pickupDay = pickups[goal] / cap;
int day = 0;
if(pickupDay <= 1 && deliveryDay <= 1){
day = 1;
afterDays(cap, day, deliveries, deliveryGoal);
afterDays(cap, day, pickups, pickupGoal);
}
else{
if(pickupDay > deliveryDay){//pickupDay 만큼은 계속 pickupGoal까지 가야함
day = pickupDay;
}
else{
day = deliveryDay;
}
afterDays(cap, day, pickups, pickupGoal);
afterDays(cap, day, deliveries, deliveryGoal);
}
answer += ((goal + 1) * day);
/*
System.out.println("goal = " + goal);
System.out.print("delivery : ");
for(int i = 0; i<deliveries.length; i++){
System.out.print(deliveries[i] + " ");
}
System.out.println();
System.out.print("pickups : ");
for(int i = 0; i<pickups.length; i++){
System.out.print(pickups[i] + " ");
}
System.out.println();
System.out.println("answer = " + answer);
*/
}
return answer*2;
}
// 1 0 0 0 0 | 11
/**
day 일동안 배달 / 수거를 진행한 이후의 list를 만든다.
*/
private void afterDays(int cap, int day, int[] list, int start){
if(start < 0)
return;
int bag = cap * day;
if(list[start] > bag){
list[start] -= bag;
return;
}
while(start >= 0){
if(list[start] < bag){
bag -= list[start];
list[start] = 0;
}
else{
list[start] -= bag;
bag = 0;
}
start--;
if(bag == 0)
return;
}
}
}⭐️ 반성
단순 구현에서 시간을 많이 낭비하는 경향이 보인다.
물론 프로그래머스에서 Exception의 위치를 출력해 주지 않아 디버깅이 어려운 것은 사실이나, 이 역시 극복해야 하는 문제이다.
특정 로직을 작성할 때, 항상 예외를 염두에 두고 System.out.println()과 return을 이용해 디버깅하는 습관을 들이는 것이 좋을 것 같다.
