Programmers에 공개된 2023 KAKAO BLIND RECRUITMENT (2023년 신입 공채 1차 온라인 코딩 테스트) 중에서 Lv.2로 설정되어 있는 택배 배달과 수거하기 문제입니다.
1. 문제 및 조건
문제
당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.
배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n)
트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다. 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.
입력
트럭에 실을 수 있는 재활용 택배 상자의 최대 개수를 나타내는 정수 cap, 배달할 집의 개수를 나타내는 정수 n, 각 집에 배달할 재활용 택배 상자의 개수를 담은 1차원 정수 배열 deliveries와 각 집에서 수거할 빈 재활용 택배 상자의 개수를 담은 1차원 정수 배열 pickups가 매개변수로 주어집니다.
1 ≤ cap ≤ 50
1 ≤ n ≤ 100,000
deliveries의 길이 = pickups의 길이 = n
deliveries[i]는 i+1번째 집에 배달할 재활용 택배 상자의 개수를 나타냅니다.
pickups[i]는 i+1번째 집에서 수거할 빈 재활용 택배 상자의 개수를 나타냅니다.
0 ≤ deliveries의 원소 ≤ 50
0 ≤ pickups의 원소 ≤ 50
트럭의 초기 위치는 물류창고입니다.
출력
트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 return한다.
입출력 예시
cap | n | delivery | 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 |
2. 설명
트럭에 최대로 실을 수 있는 상자의 개수가 cap, 집의 총 개수가 n, 각 집 사이의 거리는 1입니다. 트럭이 물류창고에서 출발해 다시 되돌아오는 구조를 하고 있기 때문에, 트럭이 한 번 나가면 같은 거리를 다시 되돌아와야 합니다. 최소한의 거리로 모든 배달 및 수거를 하기 위해서는 다음과 같은 시나리오로 배달 및 수거를 합니다.
물류창고에서 최대 용량으로 상자를 싣습니다.
배달 및 수거의 수요가 있는 집 중에서 가장 먼 곳으로 이동하면서 가장 먼 집 부터 배달을 합니다.
되돌아오면서 가장 먼 집부터 트럭의 최대 용량으로 수거를 합니다.
배달 및 수거의 수요가 없을 때 까지 반복합니다.
물류창고에서 상자를 실어 다시 물류창고까지 돌아오는 것을 한 사이클이라고 생각한다면, 트럭이 이동한 거리는 최대 거리 x 2가 됩니다. 여기서 최대 거리는 배달이나 수거의 수요 중에 한 곳이 전부 없어져도 동일합니다.
3. 해결 방식
첫 번째 해결 방법은 Stack을 사용하는 것입니다. 두 개의 Stack에 deliveries 및 pickups를 각각 오름차순으로 넣어줍니다. Stack의 LIFO(Last In First Out)특성 상 Stack의 크기가 최대 거리가 됩니다. deliveries 및 pickups의 값 범위가 0을 포함하기 때문에, 각 Stack에서 수요가 0인 것을 순서대로 뺍니다. 이후, 두 개의 Stack의 크기를 비교해 더 큰 곳이 최대 거리가 됩니다. 최대 거리를 갈 때 트럭의 최대 용량을 실어서 배달하고, 돌아올 때도 최대 용량만큼 수거를 할 것이기 때문에, 두 Stack에서 값을 빼면서 cap보다 넘어가는지 검사합니다. 만약 넘는다면 넘는 만큼 다시 Stack에 넣습니다. 두 Stack의 크기가 0이 될 때까지 반복합니다.
deliveries와 pickups를 stack에 넣습니다.
peek가 0이 아닐 때 까지 스택에서 값을 뺍니다.
최대 거리(Max distance)를 구해 최대 거리 * 2를 최종 거리에 더합니다.
각 스택에서 cap 만큼 값을 뺍니다.
2~4를 반복해 두 스택이 빌 때까지 반복합니다.
최종 거리를 return합니다.
두 번째는 deliveries를 담을 dCap이라는 변수와 pickups를 담을 pCap이라는 변수를 준비한 후, 두 배열을 역순으로 탐색하면서 각 거리에서의 상자 수를 dCap과 pCap에 더합니다. 그 후, 0 < dCap이거나 0 < pCap인 경우 해당 인덱스+1이 최대 거리가 됩니다. dCap이나 pCap이 0 미만이 될 때까지 cap만큼 빼면서 뺀 횟수를 구합니다. 그 후, 최대 거리 x 2 x 횟수를 최종 거리에 더합니다. 여기서 중요한 것은 dCap과 pCap이 마이너스가 되는 것은 해당 위치에서 배달이나 회수를 했어야 할 갯수이기 때문에 0으로 초기화하면 원하는 값을 구할 수 없게 됩니다.
deliveries와 pickups를 역순으로 탐색하면서 dCap과 pCap에 해당 인덱스의 값을 더합니다.
dCap이나 pCap이 0 이상일 경우 dCap과 pCap에 둘 다 0 미만이 될 때 까지 cap만큼 뺍니다. 그리고 (인덱스 + 1) x 2 x 횟수를 최종 거리에 더합니다.
모든 반복이 종료될 경우 최종 거리를 return합니다.
4. 코드
1. Stack을 사용하는 경우
import java.util.Stack;
public class Solution2 {
public static void main(String[] args){
Solution2 solution = new Solution2();
int cap = 2;
int n = 7;
int[] deliveries = {1, 0, 2, 0, 1, 0, 2};
int[] pickups = {0, 2, 0, 1, 0, 2, 0};
System.out.println(solution.solution(cap, n, deliveries, pickups));
}
public long solution(int cap, int n, int[] deliveries, int[] pickups) {
long answer = 0;
Stack<Integer> dStack = new Stack<>();
Stack<Integer> pStack = new Stack<>();
for(int i=0;i<n;i++){
dStack.push(deliveries[i]);
pStack.push(pickups[i]);
}
while(!dStack.isEmpty() && dStack.peek() == 0) dStack.pop();
while(!pStack.isEmpty() && pStack.peek() == 0) pStack.pop();
while(!dStack.isEmpty() || !pStack.isEmpty()){
System.out.println(dStack);
System.out.println(pStack);
int max = dStack.size() > pStack.size() ? dStack.size() : pStack.size();
answer += max * 2;
int dCap = 0;
int pCap = 0;
while(!dStack.isEmpty() && dCap <= cap) dCap += dStack.pop();
while(!pStack.isEmpty() && pCap <= cap) pCap += pStack.pop();
if(dCap > cap) dStack.push(dCap - cap);
if(pCap > cap) pStack.push(pCap - cap);
}
return answer;
}
}2. 역순 탐색의 경우
public class Solution2 {
public static void main(String[] args){
Solution2 solution = new Solution2();
int cap = 2;
int n = 7;
int[] deliveries = {1, 0, 2, 0, 1, 0, 2};
int[] pickups = {0, 2, 0, 1, 0, 2, 0};
System.out.println(solution.solution(cap, n, deliveries, pickups));
}
public long solution(int cap, int n, int[] deliveries, int[] pickups) {
long answer = 0;
int dCap = 0;
int pCap = 0;
for(int i=n-1;i>=0;i--){
int count = 0;
dCap += deliveries[i];
pCap += pickups[i];
while(dCap >= 0 && pCap >= 0){
dCap -= cap;
pCap -= cap;
count++;
}
answer += (i + 1) * 2 * count;
}
return answer;
}
}
Comments