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

이얀조·2023년 1월 11일
0

🎀프로그래머스

목록 보기
4/21
post-thumbnail

🔈 문제 설명


당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 
배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며,
배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다. 
배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다.
또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n) 
트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다. 
트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 
각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 
트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다.
각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.
트럭에 실을 수 있는 재활용 택배 상자의 최대 개수를 나타내는 정수 `cap`, 
배달할 집의 개수를 나타내는 정수 `n`, 각 집에 배달할 재활용 택배 상자의 개수를 담은 1차원 정수 배열 `deliveries`와
각 집에서 수거할 빈 재활용 택배 상자의 개수를 담은 1차원 정수 배열 `pickups`가 매개변수로 주어집니다. 
이때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 return 하도록 solution 함수를 완성해 주세요.

🕤 제한사항

  • 1 ≤ cap ≤ 50
  • 1 ≤ n ≤ 100,000
  • deliveries의 길이 = pickups의 길이 = n
    • deliveries[i]는 i+1번째 집에 배달할 재활용 택배 상자의 개수를 나타냅니다.
    • pickups[i]는 i+1번째 집에서 수거할 빈 재활용 택배 상자의 개수를 나타냅니다.
    • 0 ≤ deliveries의 원소 ≤ 50
    • 0 ≤ pickups의 원소 ≤ 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번 테스트 케이스에서 시간초과가 발생하였다.

profile
이얀조다!

0개의 댓글