문제
풀이
문제 정의
1~N까지 집이 있고, 0은 물류창고다.
각각의 집에는 배달량과 수거량이 정해져 있다.
배달량이란 해당 집에 택배를 배달해야 하는 양이고, 수거량이란 그 집에서 나온 빈 택배 박스를 수거해가야 하는 양이다.
배달 트럭에는 적재량이 정해져 있기 때문에 물류 창고에서 한 번 나갈 때 최대 cap 만큼만 택배를 실을 수 있고, 박스를 수거해올 때도 최대 cap 만큼만 실을 수 있다.
각 집마다 거리는 1씩이고, 모든 집에 배달과 수거를 완료했을 때 최소 거리를 구하는 문제다.
해결방안
우선 가장 멀리 있는 집부터 얼른 배달과 수거를 완료해야 한다. 왜냐하면 트럭에 여유 공간이 남으면 가장 멀리 있는 집으로 가는 김에 다른 집에도 택배를 배달할 수 있고, 오는 김에 다른 집의 택배를 수거할 수도 있기 때문이다.
또한 멀리 있는 집으로 가는 횟수를 최소화 해야 최소 거리를 구할 수 있기 때문이다.
첫 번째 시도
처음에는 아래와 같이 코드를 작성했다.
function solution(cap, n, deliveries, pickups) {
let answer = 0;
for(let i=n-1; i>=0; i--){
if(deliveries[i] > 0){
deliver(i,cap,deliveries);
pickup(i,cap,pickups)
answer += (i+1)*2;
}
}
return answer;
}
function deliver(n,cap,deliveries){
let count = 0;
for(let i=n; i>=0; i--){
if(cap-count >= deliveries[i]) {
count += deliveries[i];
deliveries[i] = 0;
} else {
deliveries[i] -= cap-count;
count = cap;
return;
}
}
}
function pickup(n,cap,pickups){
let count = 0;
for(let i=n; i>=0; i--){
if(cap-count >= pickups[i]) {
count += pickups[i];
pickups[i] = 0;
} else {
pickups[i] -= cap-count;
count = cap;
return;
}
}
}
멀리있는 집부터 탐색해주며 배달량이 0보다 클 경우 해당 인덱스를 기준으로 배달과 수거를 수행해준다.
deliver, pickup 함수에서는 해당 집의 배달량, 수거량을 트럭에 실을 수 있는지 여부를 판단하고 다 실을 수 있을 경우에는 다 싣고, 일부만 실을 수 있을 때는 그렇게 해주도록 했다.
하지만 아래와 같은 반례가 존재했다.
반례
cap = 2
n = 7
deliveries = [1, 0, 2, 0, 1, 0, 2]
pickups = [0, 2, 0, 1, 0, 2, 2]
correct answer: 38
wrong answer: 30solution 함수 안에서 배달량만 체크해주기 때문에 발생하는 문제였다. -> if(deliveries[i] > 0)
따라서 아래와 같이 코드를 수정해줬다.
두 번째 시도
function solution(cap, n, deliveries, pickups) {
let answer = 0;
for(let i=n-1; i>=0; i--){
if(deliveries[i] > 0 || pickups[i] > 0){
deliver(i,cap,deliveries);
pickup(i,cap,pickups)
answer += (i+1)*2;
}
}
return answer;
}
function deliver(n,cap,deliveries){
let count = 0;
for(let i=n; i>=0; i--){
if(cap-count >= deliveries[i]) {
count += deliveries[i];
deliveries[i] = 0;
} else {
deliveries[i] -= cap-count;
count = cap;
return;
}
}
}
function pickup(n,cap,pickups){
let count = 0;
for(let i=n; i>=0; i--){
if(cap-count >= pickups[i]) {
count += pickups[i];
pickups[i] = 0;
} else {
pickups[i] -= cap-count;
count = cap;
return;
}
}
}
솔루션 함수 안에서 체크해주는 부분을 이렇게 바꿨다.
if(deliveries[i] > 0) -> if(deliveries[i] > 0 || pickups[i] > 0)
하지만 역시 아래와 같은 반례가 또 있었다.
반례
cap = 1
n = 3
deliveries = [1, 0, 2]
pickups = [1, 0, 2]이는 솔루션 함수 안에 있는 for문의 범위가 n-1 ~ 0 까지로 고정되어있기 때문에 발생하는 문제다.
n-1번 집에 배달과 수거를 진행 했는데 cap이 작아서 전부 배달하지 못하거나 전부 수거하지 못하는 경우가 있을 수도 있다.
하지만 그런건 신경쓰지 않고 for문에서 i를 감소시키기 때문에 오답이 출력된다.
세 번째 시도 (통과)
function solution(cap, n, deliveries, pickups) {
let answer = 0;
// deliveries[i]와 pickups[i]가 둘 다 0일 경우 방문할 필요 없으므로 처음부터 제거해주기.
for(let i=n-1; i>=0; i--){
if(deliveries[i] === 0 && pickups[i] === 0) {
deliveries.pop();
pickups.pop();
} else break;
}
let [dLen, pLen] = [deliveries.length-1, pickups.length-1];
// 배달과 수거를 모두 끝낼 때까지 반복
while(dLen >= 0 || pLen >= 0){
let max = Math.max(dLen, pLen);
answer += (max+1)*2;
dnp(dLen,cap,deliveries);
dnp(pLen,cap,pickups);
[dLen, pLen] = [deliveries.length-1, pickups.length-1];
}
return answer;
}
function dnp(n,cap,arr){
let count = 0;
for(let i=n; i>=0; i--){
// 트럭에 다 실을 수 있는 경우
if(cap-count >= arr[i]) {
count += arr[i];
arr.pop();
}
// 일부만 실을 수 있는 경우
else {
arr[i] -= cap-count;
return;
}
}
}
코드를 많이 수정했다.
우선 deliver, pickup 함수는 dnp라는 함수로 합쳐주었다.
그리고 배달이나 수거가 끝난 집은 pop()으로 배열에서 제거해주도록 바꿨다.
이렇게 하면 arr[arr.length-1]은 배달이나 수거가 끝나지 않고, 가장 먼 집이므로 매번 마지막 인덱스만 확인해주면 된다.
