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

😙 문제 설명

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

[프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr](https://school.programmers.co.kr/learn/courses/30/lessons/150369#)

🌸 해결 과정

deliveries와 pickups 배열의 마지막 부분부터 접근하여, cap 만큼의 짐을 배달하고 수거하는 것을 반복하였다.

이 때 무작정 cap 크기의 짐을 실고 가게 되면, 다 배달하지 못하여 돌아올 때 회수할 수 있는 택배의 개수가 줄어들 것이라 생각해서 현재 deliveries에 있는 택배의 총 개수가 cap보다 작다면 총 개수만큼만 들고 가도록 설계하였다.

그리고, deliveries 와 pickups의 마지막 부분부터 탐색했을 때 0인 원소가 있다면 제외해주었다. 배달할 집과 회수할 집 중에서 가장 마지막에 있는 집을 기준으로 이동하기 때문에, deliveries와 pickups 배열 중 크기가 가장 큰 것의 두 배 (왕복 거리)를 answer에 더해주었다.

🎓 소스 코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    long long answer = 0;

    while(true) {
        if(deliveries.size() == 0 && pickups.size() == 0) break;

        // deliveries와 pickups의 뒤쪽에 있는 0을 차례로 제거한다. 
        while(deliveries.size() > 0 && deliveries.back() == 0)
            deliveries.pop_back();
        while(pickups.size() > 0 && pickups.back() == 0)
            pickups.pop_back();

        int i = deliveries.size() - 1, j = pickups.size() - 1;

        int sum = 0; 
        for(int x : deliveries){
            sum += x;
            if(sum >= cap) {
                sum = cap; 
                break;
            }
        }

        int cnt = 0;
        while(deliveries.size() > 0){
            if(deliveries[i] > 0){
                deliveries[i]--;
                cnt++;
            } else if(deliveries[i] == 0){
                if(i > 0) i--;
                else break;
            }
            if(cnt == sum) break;
        }

        cnt = 0; 
        while(pickups.size() > 0){
            if(pickups[j] > 0){
                pickups[j]--; 
                cnt++; 
            } else if (pickups[j] == 0){
                if(j > 0) j--; 
                else break;
            }
            if(cnt == cap) break;
        }

        answer += (max(deliveries.size(), pickups.size()) * 2);
    }

    return answer;
}

🧩 고찰

나는 vector로 풀면서 마지막 원소를 제거해주었지만, 이 부분을 stack 자료구조를 사용하면 더 편리해진다. 그리고, sum을 구하는 과정은 굳이 필요 없다고 할 수 있다. 남은 택배의 개수가 cap보다 작다면 자동으로 while문이 break 되기 때문에, sum 개수만큼의 택배를 실은 것이나 다름 없기 때문이다.

이 점에 착안하여 코드를 고쳐보았다.

#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> 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(), p.size()) * 2);

        int cnt = 0;
        while (!d.empty() && cnt <= cap) {
            if (d.top() + cnt <= cap)
                cnt += d.top(); 
            else {
                d.top() -= (cap - cnt); 
                break;
            }
            d.pop(); 
        }

        cnt = 0;
        while (!p.empty() && cnt <= cap) {
            if (p.top() + cnt <= cap)
                cnt += p.top();
            else {
                p.top() -= (cap - cnt);
                break;
            }
            p.pop();
        }
    }
    return answer;
}