택배 배달과 수거하기(27분)

https://school.programmers.co.kr/learn/courses/30/lessons/150369

구현 아이디어 2분 구현 25분

풀이

코딩테스트는 반례 찾기가 가장 어려운 듯... 스택을 활용하여 풀었다.

1. 스택에 배달할 집과 수거할 집을 적재한다.
2. 배달 개수와 수거 개수가 0이라면 스택에서 pop 한다.
3. 0이 아니라면 그 집은 방문해야 한다.

• 물류창고와 배달 혹은 수거할 집의 거리는 스택의 사이즈다.

4. cap이 0이 될 때까지 스택의 top을 하나씩 뺀다. 스택의 top이 0이 되면 스택에서 pop 한다.
5. 배달 거리와 수거 거리 중 더 큰 거리에 *2(왕복이기 때문에)를 하여 answer에 누적한다.

#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> delivery;
    stack<int> pickup;
    
    for(int i = 0; i < n; ++i)
    {
        delivery.push(deliveries[i]);
        pickup.push(pickups[i]);
    }
    
    while(!delivery.empty() || !pickup.empty())
    {
        // 배달부터 꺼내자.
        while(!delivery.empty())
        {
            if(delivery.top() == 0) delivery.pop();
            else break;
        }
        int tmp = cap;
        long long dist_delivery = delivery.size();
        while(true)
        {
            // tmp가 0이거나 배달할 집이 없다면 break.
            if(tmp == 0 || delivery.empty()) break;
            
            int& numDel = delivery.top();
            if(numDel != 0)
            {
                --tmp;
                --numDel;
            }
            if(numDel == 0) delivery.pop();
        }
        
        // 수거.
        while(!pickup.empty())
        {
            if(pickup.top() == 0) pickup.pop();
            else break;
        }
        tmp = cap;
        long long dist_pickup = pickup.size();
        while(true)
        {
            // tmp가 0이거나 배달할 집이 없다면 break.
            if(tmp == 0 || pickup.empty()) break;
            
            int& numPick = pickup.top();
            if(numPick != 0)
            {
                --tmp;
                --numPick;
            }
            if(numPick == 0) pickup.pop();
        }
        
        answer += (max(dist_delivery, dist_pickup) * 2);
    }
    
    return answer;
}