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

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

프로그래머스

풀이

모르겠어서 다른 분의 풀이를 봤다...

최소 이동거리로 모든 배달과 수거를 완료해야 하는데, 이 때 항상 가장 멀리 있는 우선적으로 처리하는 것이 이득임을 활용해야 한다.

1. 스택을 사용해서 배달과 회수할 수량을 각각 저장한다. (가장 멀리 있는 집이 top에 있다.)

2. 배달을 먼저 처리하는데, 어차피 가장 멀리 있는 집을 방문하므로 cap 만큼의 상자를 D 스택에서 계속해서 처리해주면 된다. 일부만 처리하는 코드 D.top() -= (cap-box) 는 cap에서 현재까지 처리한 box를 빼주어 현재 처리 할 수 있는 박스 수를 현재 집에서 빼준다.  

3. 수거에 대해서도 마찬가지로 처리한다.

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

using namespace std;

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups)
{
    long long answer = 0;
    int box = 0;     // 배송할 택배의 갯수
    stack<int> D, P; // 집 별로 배송 혹은 회수할 택배의 갯수

    for (auto i : deliveries)
        D.push(i);
    for (auto i : pickups)
        P.push(i);


    while (!D.empty() && D.top() == 0) // 집만 있고 배달할 택배는 없는 집 제거
        D.pop();
    while (!P.empty() && P.top() == 0) // 집만 있고 회수할 택배는 없는 집 제거
        P.pop();


    while (!(D.empty() && P.empty()))
    {
        answer += max(D.size() * 2, P.size() * 2); // 가장 멀리 있는 집을 먼저 방문

        box = 0;
        while (!D.empty() && box <= cap)
        {
            if (D.top() + box <= cap) // D.top() 집에 배송할 택배를 전부 실을 수 있을 때
                box += D.top();
            else
            {
                D.top() -= (cap - box); // 일부만 실을 때
                break;
            }
            D.pop();
        }

        box = 0;
        while (!P.empty() && box <= cap)
        {
            if (P.top() + box <= cap) // P.top() 집에서 회수할 택배를 전부 실을 수 있을 때
                box += P.top();
            else
            {
                P.top() -= (cap - box); // 일부만 실을 때
                break;
            }
            P.pop();
        }
    }
    return answer;
}