[JavaScript] 2023 KAKAO BLIND RECRUITMENT - 택배 배달과 수거하기
Q. 문제
당신은 일렬로 나열된 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개 |
배달 및 수거 과정
| 집 | 집 #1 | 집 #2 | 집 #3 | 집 #4 | 집 #5 | 설명 |
| 남은 배달/수거 | 1/0 | 0/3 | 3/0 | 1/4 | 2/0 | 물류창고에서 택배 3개를 트럭에 실어 출발합니다. |
| 남은 배달/수거 | 1/0 | 0/3 | 3/0 | 0/4 | 0/0 | 물류창고에서 5번째 집까지 이동하면서(거리 5) 4번째 집에 택배 1개를 배달하고, 5번째 집에 택배 2개를 배달합니다. |
| 남은 배달/수거 | 1/0 | 0/3 | 3/0 | 0/0 | 0/0 | 5번째 집에서 물류창고까지 이동하면서(거리 5) 4번째 집에서 빈 택배 상자 4개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내리고 택배 4개를 트럭에 싣습니다. |
| 남은 배달/수거 | 0/0 | 0/3 | 0/0 | 0/0 | 0/0 | 물류창고에서 3번째 집까지 이동하면서(거리 3) 1번째 집에 택배 1개를 배달하고, 3번째 집에 택배 3개를 배달합니다. |
| 남은 배달/수거 | 0/0 | 0/0 | 0/0 | 0/0 | 0/0 | 3번째 집에서 물류창고까지 이동하면서(거리 3) 2번째 집에서 빈 택배 상자 3개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내립니다. |
16(=5+5+3+3)의 거리를 이동하면서 모든 배달 및 수거를 마쳤습니다. 같은 거리로 모든 배달 및 수거를 마치는 다른 방법이 있지만, 이보다 짧은 거리로 모든 배달 및 수거를 마치는 방법은 없습니다.
트럭에 실을 수 있는 재활용 택배 상자의 최대 개수를 나타내는 정수 cap, 배달할 집의 개수를 나타내는 정수 n, 각 집에 배달할 재활용 택배 상자의 개수를 담은 1차원 정수 배열 deliveries와 각 집에서 수거할 빈 재활용 택배 상자의 개수를 담은 1차원 정수 배열 pickups가 매개변수로 주어집니다. 이때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 return 하도록 solution 함수를 완성해 주세요.
* 문제풀이흐름
1. 처음엔 맨 뒤에서 cap만큼 각각 deliveries, pickups의 상자 개수를 빼주고 제일 멀리 있던 index를 저장해 *2를 했었음
2. 근데 이렇게 하면 모든 배달과 수거를 완료할 때까지 계속 n번의 루프를 돌아야함
=> 당연히 시간초과 났음 => 그래서 한번만 순회하는 코드 작성
3. 마찬가지로 맨 뒤에서부터 시작
4. deliver + deliveries[i]로 배달할 상자가 존재할 때( deliver > 0 )
5. deliver - cap하여 양수면 한번 더 왕복 이동해야함
5. 음수라면 deliver + deliveries[i]를 통하여 배달 가능한 만큼 완료하기
6. 다시 deliver > 0가 되면 해당 거리만큼 왕복 이동
A. 풀이(첫시도)
function solution(cap, n, deliveries, pickups) {
var answer = 0;
while(true) {
let deliver = cap
let pickup = cap
let move = 0
for(let i = n - 1; i >= 0; i--) {
if(deliver >= deliveries[i] && deliveries[i] !== 0) {
deliver -= deliveries[i]
deliveries[i] = 0
if(move < i+1) {
move = i+1
}
}
if(pickup >= pickups[i] && pickups[i] !== 0) {
pickup -= pickups[i]
pickups[i] = 0
if(move < i+1) {
move = i+1
}
}
}
answer += move * 2
if(deliveries.every(item => item === 0) && pickups.every(item => item === 0)) break;
}
return answer;
}
A. 정답
function solution(cap, n, deliveries, pickups) {
let answer = 0;
let deliver = 0;
let pickup = 0;
for (let i = n - 1; i >= 0; i--) {
deliver += deliveries[i];
pickup += pickups[i];
while (deliver > 0 || pickup > 0) {
deliver -= cap;
pickup -= cap;
answer += (i + 1) * 2;
}
}
return answer;
}