Programmersに公開された2023 KAKAO BLIND RECRUITMENT（2023年新入債務第一次オンラインコーディングテスト）の中でLv.2に設定されている宅配配達と收去問題です。
1. 問題と条件
問題
貴方は一列に並んでいるｎ個の家に宅配を配達しようとしています。配達する物は全て大きさが同じ財活用宅配箱に入れて配達して、配達に行きながら空っぽの財活用宅配箱たちを收去しようとしています。
配達する宅配たちは全て財活用宅配箱に入れて物流倉庫に保管されていて、i番目の家は物流倉庫から距離i分離れています。またi番目の家はj番目の家と距離j - i分離れていあす。（1 ≤ i ≤ j ≤ n）
トラックには財活用宅配箱を最大cap個乗っけられます。トラックに配達する財活用宅配箱たちを乗っけて物流倉庫から出発し各家に配達しながら、空っぽの財活用宅配箱たちを收去して物流倉庫に入れます。各家の配達する財活用宅配箱の個数と收去する空っぽの財活用宅配箱の個数を知っている時、トラック一個で全ての配達と收去を終えて物流倉庫まで戻れる最小移動距離を出したいです。各家に配達と收去をする時、求める数の分宅配を配達と收去ができます。
入力
トラックに乗っけれる財活用宅配箱の最大個数を表す定数cap、配達する家の個数を表定数ｎ、各家に配達する財活用宅配箱の個数を入れた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、各家の間の距離は１です。トラックが物流倉庫から出発して戻って来る構造なので、トラックが一回出たら同じ距離を移動しないといけないです。最小の距離で全ての配達と收去をする為には下記のようなシナリオで配達と收去をします。
物流倉庫で最大容量で箱を乗っけます。
配達と配達と收去の需要がある家の中で一番遠いところに移動しながら一番遠い家から配達します。
帰って来ながら一番遠い家からトラックの最大容量で收去をします。
配達と收去の需要時まで繰り返します。
物流倉庫から箱を乗っけて配達と收去をして帰って来ることを一つのサイクルだと考えたら、トラックが移動した距離は「最大距離x２」になります。ここで最大距離は配達と收去のどっちかの需要が無くなっても同じです。
3. 解決方法
１番目の解決方法はStackを使用することです。二つのStackにdeliveriesとpickupsをそれぞれ昇順で入れます。StackのLIFO(Last In First Out)の特性上Stackの大きさが最大距離になります。deliveriesとpickupsの範囲が0を含めるため、各Stackからpeekの値が０であることを順番に抜けます。その後2個のStackの大きさを比べてもっと大きのが最大距離になります。最大距離を行く時トラックの最大容量を乗っけて配達して、帰る時も最大容量で收去をするので、二つのStackから値を抜けながらcapより大きくなるのか検査します。もし大きくなったらcapだけ持つようにしてStackにまた入れます。二つのStackの大きさが０になるまで繰り返します。
deliveriesとpickupsをstackに入れます。
peekが0じゃない時までstackから値を抜けます。
最大距離（Max distance）を出して最大距離x２を最終距離に合わせます。
各stackからcapの分値を抜けます。
2〜４を二つのstackが空っぽになるまで繰り返します。
最終距離をreturnします。
２番目はdeliveriesを入れるdCap変数とpickupsを入れるpCap変数を準備した後、二つの配列を逆に検索しながら各距離での箱の数をdCapとpCapに合わせます。その後、0 < dCapであるか0 < pCapになる場合のインデックス＋１が最大距離になります。dCapとか pCapが０未満になるまでcapの分抜けながら抜いた回数を出します。その後、最大距離x２x回数を最終距離に合わせます。ここで重要なのはdCapとpCapがマイナスになるのは
その位置で配達や收去をするべきだった個数なので、０に初期化したら求める値を救うのができません。
deliveriesとpickupsを逆に検索しながらdCapとpCapにそのインデックスにある値を合わせます。
dCapやpCapが ０以上である場合dCapとpCapが０未満になるまでcapの分抜けます。そして（インデックス＋１）x２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