문제를 어떻게 접근해야하는지 40분간 고민했지만
결국 Greedy로 끝집부터 수거해야한다는 방법, 그리고 각 조건에 대한
명확한 풀이가 떠오르지 않았습니다.
일단 문제에 주어진 첫 번째 예시에서 truck에 최대의 박스를 싣지 않고
수거할 수 있는 만큼만 싣는 것처럼 되어 있어서 그 부분에 대해서 구현하려고 오랜 시간을 썼습니다. 그러나 그 부분이 낚시?성 예시였던것 같습니다.
아래를 예시로 들어 접근 방법을 설명하겠습니다. (cap=4)
Stack을 이용합니다.
각 집마다 옮겨야하는 박스를 Stack에 넣고 넣을 때 각 집의 위치를 박스 수만큼 넣습니다.
마찬가지로 각 집마다 수거해야할 박스를 Stack에 넣고 넣을 때 각 집의 위치를 박스 수만큼 넣습니다.
이제 각 Stack에서 cap의 수만큼 함께 꺼냅니다.
각 Stack이 비어질 때까지 함께 꺼냅니다.
또한 처음 꺼낸 집의 위치 중에서 큰 것을 고릅니다. 왜냐하면 그 집이 처음에 들린 집이고 그 집부터 아래로 내려오면 택배를 주고 수거해야하기 때문입니다.
두 번째 예시의 경우 (cap=2)
아래의 모양을 가지게 됩니다.
cap이 2인 경우
위와 같이 Pstack과 Dstack이 함께 파란색까지 진행되고 이후 Dstack이 남은 경우에는 남겨진 택배를 옮겨야하기 때문에 혼자서 진행됩니다.
import java.util.*;
class Solution {
public long solution(int cap, int n, int[] deliveries, int[] pickups) {
long answer = 0;
//n개의 집에 택배를 배달
// 배달할 물건 모두 크기가 같은 재활용 택배 상자에 담아 배달
// 배달을 다니면서 빈 재활용 택배 상자 수거
// 트럭에는 재활용 택배 상자를 최대 cap개
// 각 집마다 배달할 택배상자, 수거할 빈 택배상자의 개수
// 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동거리
// 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있다.
Stack<Integer> Dstack = new Stack<Integer>();
Stack<Integer> Pstack = new Stack<Integer>();
for(int i=0;i<n;i++){
for(int j=0;j<deliveries[i];j++){
Dstack.push(i+1);
}
for(int j=0;j<pickups[i];j++){
Pstack.push(i+1);
}
}
while(!Dstack.isEmpty() && !Pstack.isEmpty()){
int Dhouse =Dstack.peek();
int Phouse =Pstack.peek();
for(int i=0;i<cap;i++){
if(!Dstack.isEmpty()) Dstack.pop();
if(!Pstack.isEmpty()) Pstack.pop();
}
answer+=Math.max(Dhouse,Phouse)*2L;
}
while(!Dstack.isEmpty()){
int Dhouse =Dstack.peek();
for(int i=0;i<cap;i++){
if(!Dstack.isEmpty()) Dstack.pop();
}
answer+=Dhouse*2L;
}
while(!Pstack.isEmpty()){
int Phouse =Pstack.peek();
for(int i=0;i<cap;i++){
if(!Pstack.isEmpty()) Pstack.pop();
}
answer+=Phouse*2L;
}
return answer;
}
}