문제설명
당신은 일렬로 나열된 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≤ 50 - 1 ≤
n≤ 100,000 deliveries의 길이 =pickups의 길이 =ndeliveries[i]는 i+1번째 집에 배달할 재활용 택배 상자의 개수를 나타냅니다.pickups[i]는 i+1번째 집에서 수거할 빈 재활용 택배 상자의 개수를 나타냅니다.- 0 ≤
deliveries의 원소 ≤ 50 - 0 ≤
pickups의 원소 ≤ 50
- 트럭의 초기 위치는 물류창고입니다.
입출력 예
| cap | n | deliveries | pickups | result |
|---|---|---|---|---|
| 4 | 5 | [1, 0, 3, 1, 2] | [0, 3, 0, 4, 0] | 16 |
| 2 | 7 | [1, 0, 2, 0, 1, 0, 2] | [0, 2, 0, 1, 0, 2, 0] | 30 |
입출력 예 설명
입출력 예 #1
- 문제 예시와 동일합니다.
입출력 예 #2
배달 및 수거할 재활용 택배 상자 개수
| 집 #1 | 집 #2 | 집 #3 | 집 #4 | 집 #5 | 집 #6 | 집 #7 | |
|---|---|---|---|---|---|---|---|
| 배달 | 1개 | 0개 | 2개 | 0개 | 1개 | 0개 | 2개 |
| 수거 | 0개 | 2개 | 0개 | 1개 | 0개 | 2개 | 0개 |
배달 및 수거 과정
| 집 #1 | 집 #2 | 집 #3 | 집 #4 | 집 #5 | 집 #6 | 집 #7 | 설명 | |
|---|---|---|---|---|---|---|---|---|
| 남은 배달/수거 | 1/0 | 0/2 | 2/0 | 0/1 | 1/0 | 0/2 | 2/0 | 물류창고에서 택배 2개를 트럭에 실어 출발합니다. |
| 남은 배달/수거 | 1/0 | 0/2 | 2/0 | 0/1 | 1/0 | 0/2 | 0/0 | 물류창고에서 7번째 집까지 이동하면서(거리 7) 7번째 집에 택배 2개를 배달합니다. |
| 남은 배달/수거 | 1/0 | 0/2 | 2/0 | 0/1 | 1/0 | 0/0 | 0/0 | 7번째 집에서 물류창고까지 이동하면서(거리 7) 6번째 집에서 빈 택배 상자 2개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내리고 택배 2개를 트럭에 싣습니다. |
| 남은 배달/수거 | 1/0 | 0/2 | 1/0 | 0/1 | 0/0 | 0/0 | 0/0 | 물류창고에서 5번째 집까지 이동하면서(거리 5) 3번째 집에 택배 1개를 배달하고, 5번째 집에 택배 1개를 배달합니다. |
| 남은 배달/수거 | 1/0 | 0/1 | 1/0 | 0/0 | 0/0 | 0/0 | 0/0 | 5번째 집에서 물류창고까지 이동하면서(거리 5) 4번째 집에서 빈 택배 상자 1개를 수거하고 2번째 집에서 빈 택배 상자 1개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내리고 택배 2개를 트럭에 싣습니다. |
| 남은 배달/수거 | 0/0 | 0/1 | 0/0 | 0/0 | 0/0 | 0/0 | 0/0 | 물류창고에서 3번째 집까지 이동하면서(거리 3) 1번째 집에 택배 1개를 배달하고, 3번째 집에 택배 1개를 배달합니다. |
| 남은 배달/수거 | 0/0 | 0/0 | 0/0 | 0/0 | 0/0 | 0/0 | 0/0 | 3번째 집에서 물류창고까지 이동하면서(거리 3) 2번째 집에서 빈 택배 상자 1개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내립니다. |
30(=7+7+5+5+3+3)의 거리를 이동하면서 모든 배달 및 수거를 마쳤습니다. 같은 거리로 모든 배달 및 수거를 마치는 다른 방법이 있지만, 이보다 짧은 거리로 모든 배달 및 수거를 마치는 방법은 없습니다.
따라서, 30을 return 하면 됩니다.
출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
설계 과정
어떤 생각으로 설계했는지 간단히 말해보겠다.
배달을 할때는 최대한 많이 들고가서 일단 배달할 곳이 남은 곳까지 이동하면서 뒤에서부터 나눠준다고 생각하면 편하다.
-> 실제로는 끝 집까지 출발하면서 나눠줌.
수거할때는 0개에서 시작해서 최대한 많이 수거해오면 된다.
뒤에서부터 수거 배열의 값이 0이 될때까지 가져온다고 생각하면 된다.
-> 이런 논리라면 배달과정과 수거 과정이 똑같다. (아래 설계에서 함수를 2개 만들긴 했지만 코드는 똑같다)
그리고 이동거리 같은 경우는 배달을 하던 수거를 하던 일단 제일 멀리 할게 남은 곳이라면 거기까지 가야 한다. 따라서 배달 거리와 수거 거리 중에 큰 것이 이동거리이다.
이를 위해서 함수를 만들때 뒤에서부터 cap만큼을 최대한 지워주고, cap을 다 썼거나 지울게 없다면 조사했던 가장 먼 집에 인덱스를 리턴하는 함수가 필요하다.
그리고 추가로 시간복잡도를 생각한다면 뒤에가 0인 값들은 pop을 통해서 없애주는 것이 좋다.
- 우선 함수를 3개 만들었다.
- 배열의 뒤에서부터 0인 값은 pop해버리고, 0이 아닌 마지막 index를 리턴 하는 함수
- 배달 함수
-> 인자: 배달 배열, cap
들고 갈 수 있는 만큼 가져가서 뒤부터 cap만큼을 계속 빼줌.
[2,4,1,3,2] , cap: 4 => [2,4,1,1,0]으로 만들어주고, 처음에 조사를 시작했던 마지막 index를 리턴- 수거 함수
수거 함수도 위와 마찬가지로 구현 넣는 인자만 달라짐.
- 위의 함수를 가지고 아래 과정을 수행
1) 배달함수를 실행 해줌과 동시에 마지막 조사 집의 인덱스를 받아줌. (delLen)
2) 수거함수를 실행 해줌과 동시에 마지막 조사 집의 인덱스를 받아줌. (pickLen)
3) 이 둘을 비교 해서 둘다 0이면 answer+1을 리턴
4) 같지 않다며 둘 중에 큰거에 *2해서 answer에 더해줌.
정답 코드
function solution(cap, n, deliveries, pickups) {
var answer = -1;
//배열 마지막부터 0이 아닌곳 찾기 전부 0이면 -1을 리턴
function lastFun(arr){
var len = arr.length;
for(var i = len-1;i>=0;i--){
if(arr[i]!==0){
return i;
}
else{
arr.pop();
}
}
return -1;
}
//deliveries을 받는다고 가정
function delFun(arr,cap){
var index = lastFun(arr);
var checkIndex = index;
while(index!==-1 && cap>0){
var index = lastFun(arr);
// cap보다 그 요소의 값이 크다면 요소의 값만 빼주고 돌아감 종료
if(cap<=arr[index]){
arr[index] -= cap;
cap = 0;
break;
}
// cap보다 작다면 cap에서 그 요소 빼주고, 그 값을 0으로 돌림
else if(cap>arr[index]){
cap-=arr[index];
arr[index] = 0;
index--;
}
}
// 결론적으로 나올때는 배달 완료 된 것 배열이 튀어나옴.
//console.log(index,arr);
return checkIndex;
}
function pickFun(arr,cap){
var index = lastFun(arr);
var checkIndex = index;
while(index!==-1 && cap>0){
var index = lastFun(arr);
// cap보다 그 요소의 값이 크다면 요소의 값만 빼주고 돌아감 종료
if(cap<=arr[index]){
arr[index] -= cap;
cap = 0;
break;
}
// cap보다 작다면 cap에서 그 요소 빼주고, 그 값을 0으로 돌림
else if(cap>arr[index]){
cap-=arr[index];
arr[index] = 0;
index--;
}
}
// 결론적으로 나올때는 배달 완료 된 것 배열이 튀어나옴.
//console.log(index,arr);
return checkIndex;
}
while(true){
var delLen = delFun(deliveries,cap) + 1;
var pickLen = pickFun(pickups,cap) + 1;
if(delLen === 0 && pickLen === 0){
return answer + 1;
}
else if(delLen>pickLen){
answer+=delLen * 2;
}
else{
answer+=pickLen *2;
}
}
}결과
이번 문제는 문제가 길고 복잡한 만큼 크게 3덩어리로 나눠서 따로 생각해보았다. 그 덕분에 헷갈리지 않고 금방 풀었던 문제였다.
