[프로그래머스][C++] 택배 배달과 수거하기

택배 배달과 수거하기

문제 링크

택배 배달과 수거하기

분석

n은 배달할 집의 개수를 나타내는 정수입니다.

pickups[i]는 i+1번째 집에서 수거할 빈 재활용 택배 상자의 개수를 나타냅니다.
deliveries[i]는 i+1번째 집에 배달할 재활용 택배 상자의 개수를 나타냅니다.

cap은 트럭에 실을 수 있는 재활용 택배 상자의 최대 개수를 나타내는 정수입니다.
즉, 한번에 최대 cap개의 물건을 배달하거나 수거할 수 있습니다.

i번째 집은 i번째 만큼 떨어져 있습니다.
i반째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다.

택배 기사는 0번 집에서 출발하여, 각 집을 방문하며 배달과 수거를 수행하고, 다시 0번 집으로 돌아옵니다.

트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 반환해야합니다.

풀이

#include <vector>

using namespace std;

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    long long answer = 0;
    
    // 배달과 수거의 남은 수량을 저장한다.
    int deliveryCap = 0;
    int pickupCap = 0;
    
    for (int i = n - 1; i >= 0; --i)
    {
        // 배달과 수거해야 할 수량을 누적한다.
        deliveryCap += deliveries[i];
        pickupCap += pickups[i];
        
        // 현재까지 누적된 배달 또는 수거 요청이 하나라도 있는 경우
        while (deliveryCap > 0 || pickupCap > 0)
        {
            // 한 번 왕복할 때, 트럭이 배달하고, 수거하는 최대량을 빼줍니다.
            deliveryCap -= cap;
            pickupCap -= cap;
            
            // i번 집까지 갔다 오는 왕복 거리 누적
            // i는 0-based이므로 i + 1이 실제 거리입니다.
            answer += static_cast<long long>(i + 1) * 2;
        }
    }
    
    return answer;
}

트럭이 배달하고, 수거하는 누적량을 뺄 때, 음수로 내려가는 것을 허용하는 이유는 음수일 경우 i - 1번째의 배달과 수거를 일부분 했다고 가정하여 연산하기 위함입니다.

성능 요약

시간 복잡도는 $O(n \times k)$입니다.

• 각 집을 순회하는 반복문 $O(n)$
• 각 집에서 배달이나 수거하는 반복문 $O(k)$
  • k는 최대 deliveryCap + pickupCap / cap번 반복됩니다.
• $O(n \times k)$

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

테스트 성능

테스트 1 〉 통과 (0.01ms, 4.21MB)
테스트 2 〉 통과 (0.01ms, 4.14MB)
테스트 3 〉 통과 (0.01ms, 4.21MB)
테스트 4 〉 통과 (0.01ms, 3.66MB)
테스트 5 〉 통과 (0.01ms, 4.2MB)
테스트 6 〉 통과 (0.01ms, 3.68MB)
테스트 7 〉 통과 (0.02ms, 4.19MB)
테스트 8 〉 통과 (0.02ms, 4.02MB)
테스트 9 〉 통과 (0.05ms, 4.14MB)
테스트 10 〉 통과 (0.05ms, 4.2MB)
테스트 11 〉 통과 (0.04ms, 4.15MB)
테스트 12 〉 통과 (0.04ms, 4.2MB)
테스트 13 〉 통과 (0.03ms, 4.16MB)
테스트 14 〉 통과 (0.03ms, 4.2MB)
테스트 15 〉 통과 (0.57ms, 9.66MB)
테스트 16 〉 통과 (2.43ms, 9.64MB)
테스트 17 〉 통과 (1.29ms, 9.54MB)
테스트 18 〉 통과 (0.88ms, 9.5MB)
테스트 19 〉 통과 (0.84ms, 9.64MB)
테스트 20 〉 통과 (0.87ms, 9.58MB)