프로그래머스 택배 배달과 수거(자바) - 카카오
문제 설명
당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.
배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n)
트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다. 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.
다음은 cap=4 일 때, 최소 거리로 이동하면서 5개의 집에 배달 및 수거하는 과정을 나타낸 예시입니다.
배달 및 수거할 재활용 택배 상자 개수
집 #1집 #2집 #3집 #4집 #5배달 | 1개 | 0개 | 3개 | 1개 | 2개 |
수거 | 0개 | 3개 | 0개 | 4개 | 0개 |
처음에는 맨 끝 인덱스로 가서 for 문으로 맨 앞 인덱스로 가면서 수거와 배달을 수행하는 과정을 반복해서 시간 초과가 발생했다.
그래서 아래의 다른 사람이 푼 풀이를 보고 공부했다.
이 코드는 계속해서 for문을 반복하는게 아니라
맨 끝 인덱스부터 for문을 돌리면서 그 인덱스의 위치에 트럭이 몇번 오게 되는지 카운트 한 후에 거리를 계산해서 더해주는 방식으로 풀이했다.
class Solution {
public long solution(int cap, int n, int[] deliveries, int[] pickups) {
long answer = 0;
int deliver = 0;
int pickup = 0;
for (int i = n-1; i >= 0; i--) {
if (deliveries[i] > 0 || pickups[i] > 0) {
int cnt = 0;
while (deliver < deliveries[i] || pickup < pickups[i]) {
//[i] 인덱스 위치를 몇 번 방문할지 카운트
cnt++;
deliver += cap;
pickup += cap;
}
deliver -= deliveries[i]; //남은 트럭 자리 계산
pickup -= pickups[i];
answer += (i+1) * cnt * 2;
}
}
return answer;
}
}