당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다.
배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며,
배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.
배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다.
또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n)
트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다.
트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다.
각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때,
트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다.
각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.
트럭에 실을 수 있는 재활용 택배 상자의 최대 개수를 나타내는 정수 `cap`,
배달할 집의 개수를 나타내는 정수 `n`, 각 집에 배달할 재활용 택배 상자의 개수를 담은 1차원 정수 배열 `deliveries`와
각 집에서 수거할 빈 재활용 택배 상자의 개수를 담은 1차원 정수 배열 `pickups`가 매개변수로 주어집니다.
이때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 return 하도록 solution 함수를 완성해 주세요.
cap
≤ 50n
≤ 100,000deliveries
의 길이 = pickups
의 길이 = ndeliveries[i]
는 i+1번째 집에 배달할 재활용 택배 상자의 개수를 나타냅니다.pickups[i]
는 i+1번째 집에서 수거할 빈 재활용 택배 상자의 개수를 나타냅니다.deliveries
의 원소 ≤ 50pickups
의 원소 ≤ 50이 문제의 포인트는 두가지라고 생각하였다.
cap
)이 비어있다고 가정할 수 있다는 것따라서 먼 거리 부터 deliveries[i]
와 pickups[i]
를 체크하였으며 픽업시에는 cap
의 범위를 특별하게 고려하지 않고 택배상자가 비었다고 가정하여 픽업하였다.
이 문제 또한 복잡한 알고리즘적 능력을 요구하지는 않지만 해결하는 과정에서 시간초과가 잘 나는 문제였던 만큼 위의 두 포인트를 어느정도 인지하고 있다면 절반은 간 문제라고 생각한다.
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
long long answer = 0;
stack<int> sDeliver, sPick;
for (int i = 0; i < deliveries.size(); i++) {
if (deliveries[i] > 0) sDeliver.push(i);
if (pickups[i] > 0) sPick.push(i);
}
int idxDel = -1, idxPick = -1;
while(!sDeliver.empty() || !sPick.empty()) {
int nowDel = cap, nowPick = 0;
if (!sDeliver.empty()) idxDel = sDeliver.top();
if (!sPick.empty()) idxPick = sPick.top();
answer += (max(idxDel, idxPick) + 1) * 2;
// Deliver
if (!sDeliver.empty()) {
for (int i = idxDel; i >= 0; i--) {
if (nowDel <= 0) break;
if (nowDel > 0 && deliveries[i] > 0) {
if (nowDel >= deliveries[i]) {
nowDel -= deliveries[i];
deliveries[i] = 0;
}
else {
deliveries[i] -= nowDel;
nowDel = 0;
}
}
}
}
// Pick
if (!sPick.empty()) {
for (int j = idxPick; j >= 0; j--) {
if (nowPick >= cap) break;
if (nowPick < cap && pickups[j] > 0) {
if (cap - nowPick >= pickups[j]) {
nowPick += pickups[j];
pickups[j] = 0;
}
else {
pickups[j] -= (cap - nowPick);
nowPick = cap;
}
}
}
}
idxDel = -1; idxPick = -1;
// set Next Idx
while(!sDeliver.empty()) {
if (deliveries[sDeliver.top()] <= 0) sDeliver.pop();
else break;
}
while(!sPick.empty()) {
if (pickups[sPick.top()] <= 0) sPick.pop();
else break;
}
}
return answer;
}
1. 시간초과
→ 기존에 작성하였던 코드에서는 시간초과가 발생하였고, stack을 이용하여 deliver, pickup 각각 필요한 부분을 따로 구하여 탐색하였다.
→ 특히 더이상 Deliver 할 수 없거나 Pick up 할 수 없는 경우를 체킹하지 않으면 16번 테스트 케이스에서 시간초과가 발생하였다.