문제
풀이
- 인터넷에 우선순위 큐, 그리디 등 다양한 알고리즘 문제라고 소개되어 있지만 내가 스스로 풀어본 결과 약간의 센스가 필요한 단순한 구현 문제 같았다.
- 해당 문제를 풀 때 주의해야 할 점은 2가지가 있었다.
- 코드 초반에 deliveries 배열과 pickups 배열을 뒤에서부터 순회하면서 두 배열의 초기값이 모두 0인 경우 n을 줄여줘야 한다. (테스트 2)
- 시간 초과가 나지 않게 deliveries 배열과 pickups 배열의 맨 뒤 인덱스 값이 0이 될 경우 바로 pop 해준다. (테스트 16)
- 전체적인 풀이 방법은 deliveries 배열과 pickups 배열을 뒤에서부터 순회하면서 배달와 수거를 최대한으로 수행해주면 된다. 이때 거리는 항상 같은 거리를 2번 이동한다. (갈 때와 다시 돌아올 때)
- 또한, 거리를 deliveries 배열과 pickups 배열 중 더 긴 거리로 업데이트해준다.
소스 코드
function solution(cap, n, deliveries, pickups) {
let answer = 0;
while(n > 0 && deliveries[n - 1] === 0 && pickups[n - 1] === 0) {
deliveries.pop();
pickups.pop();
n -= 1;
}
while(true) {
let cnt = cap;
for (let i = deliveries.length - 1; i >= 0; i--) {
if (deliveries[i] <= cnt) {
cnt -= deliveries[i];
deliveries[i] = 0;
deliveries.pop();
} else {
deliveries[i] -= cnt;
cnt = 0;
break;
}
}
cnt = cap;
for (let i = pickups.length - 1; i >= 0; i--) {
if (pickups[i] <= cnt) {
cnt -= pickups[i];
pickups[i] = 0;
pickups.pop();
} else {
pickups[i] -= cnt;
cnt = 0;
break;
}
}
answer += (n * 2);
n = Math.max(pickups.length, deliveries.length);
if (n <= 0) break;
}
return answer;
}