프로그래머스 택배 배달과 수거하기 (c++)

고리·2023년 1월 6일
0

알고리즘

목록 보기
3/4
post-thumbnail

  • 프로그래머스
  • 택배 배달과 수거하기
  • 2023 KAKAO BLIND RECRUITMENT
  • c++

(문제링크)

전체 코드

#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;
}

구글에 풀이가 없길래 직접 작성해보려 한다.

문제를 다 읽고서 그리디 알고리즘 이라고 생각했다. 배달/수거와 관계없이 가장 멀리있는 집을 방문해야하기 때문이다.

가장 멀리있는 집을 방문하는 선택이 최선의 선택이고, 이 선택이 곧 전체 문제에서도 최선의 선택이다.

문제에도 여러 예제가 제시되어 있긴 하지만 직접 예제를 만들어 보면 더 이해하기 쉽다.

Cap: 5
n: 5

Deliveries: 15 20 25 0 35
Pickups: 10 0 5 35 20

이렇게 만들었을 때 배송/수거 택배 수의 흐름을 보면 다음과 같다.

두번째 줄만 설명하면 5번 집에 7번 택배를 배송할 동안 5번 집의 택배를 4번 회수하고 4번 집의 택배를 3번 회수한다.


문제 풀이

이제 코드 별로 설명을 해보자

stack<int> D, P;

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

앞서서 가장 멀리 있는 집을 방문하는 것이 최선의 선택이고 결국 모든 집을 방문해서 택배를 배달/수거 해야한다. 가장 멀리 있는 집의 택배를 회수해야 두번째로 멀리 있는 집의 택배를 회수할 수 있기 때문에 스택을 생각했다.


1시간 삽질한 부분

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

여기서 거의 한시간을 날렸는데 아래와 같은 case를 생각해야 한다.

cap: 2
n: 2
deliveries = [1, 0]
pickups = [1. 0]

이 코드는 가장 멀리 있는 집을 방문하기 때문에 방문할 필요가 없는, 즉 배달/회수할 택배가 없는 집은 고려 대상에서 제외해야 한다.


문제의 핵심 알고리즘

    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();
        }
    }

처음 등장하는 반복문은 모든 집에 배송/회수가 완료될 때 까지 while loop를 도는 것을 의미한다.

두번째, 세번째 등장하는 반복문은 각 집에서 배송/회수할 택배를 정하는 부분이다. box 변수가 현재까지 담은 박수의 개수를 의미하기 때문에 cap을 넘지 않을 때 까지 택배를 계속 담을 수 있다.

while문 안의 if-else 문은 cap은 5인데 가장 멀리있는 집에 배송/회수할 택배는 6개인, 즉 해당 집의 택배를 일부만 배송/수거할 경우를 나눠준것이다.

일부만 배송/수거한다면 pop을 통해 해당 집을 고려대상에서 제외하면 안되기 때문에 break;를 통해 반복문을 탈출시켜 주었다.


쉬워보였는데 시간을 어마어마하게 쓴 문제였다!

profile
Back-End Developer

0개의 댓글