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

프로그래머스

 

• 배달/수거해야 하는 물건이 i번째에 하나라도 있다면 i까지는 가야함
• 한 싸이클마다 cap만큼의 배달/수거가 가능
• 싸이클 후 i에 택배가 남아있다면 다시 i로 가야함
• 매 싸이클마다 가장 멀리있는 집부터 해결해야함

 

탐욕법까지는 떠올렸으나 구현 단계에서 시간이 꽤 걸렸다.

#include <string>
#include <vector>
#include <stack>

using namespace std;

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    long long answer = 0;
    
    stack<int> deliver, pickup;
    
    // 가까운 곳에서부터 i + 1의 거리에 위치한 집에 배달/수거해야 하는 물품 수만큼 스택에 해당 집의 거리를 삽입
    // 각각 스택의 top에는 가장 먼 거리가 저장
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < deliveries[i]; j++) 
            deliver.push(i + 1);
        for(int j = 0; j < pickups[i]; j++)
            pickup.push(i + 1);
    }
    
    // deliver 또는 pickup 스택이 비어있지 않다면 배달/수거 필요
    while(!deliver.empty() || !pickup.empty()) {
        int distDeliver = 0, distPickup = 0;
        
        // 한 번 출발 시 cap만큼 배달과 수거가 가능
        for(int i = 0; i < cap; i++) {
            // deliver 스택이 비어있지 않다면
            if(!deliver.empty()) {
                if(i == 0) distDeliver = deliver.top();
                deliver.pop();   
            }
            
            // pickup 스택이 비어있지 않다면
            if(!pickup.empty()) {
                if(i == 0) distPickup = pickup.top();
                pickup.pop();
            }
        }
        
        // 한 번 출발 시 둘 중 더 먼 거리까지 왕복하는 것이 한 싸이클이기 때문에 더 큰 값 x 2를 answer에 더함
        answer += max(distDeliver, distPickup) * 2;
    }
    
    return answer;
}