- 프로그래머스
- 택배 배달과 수거하기
- 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: 5Deliveries: 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);
앞서서 가장 멀리 있는 집을 방문하는 것이 최선의 선택이고 결국 모든 집을 방문해서 택배를 배달/수거 해야한다. 가장 멀리 있는 집의 택배를 회수해야 두번째로 멀리 있는 집의 택배를 회수할 수 있기 때문에 스택을 생각했다.
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;를 통해 반복문을 탈출시켜 주었다.
쉬워보였는데 시간을 어마어마하게 쓴 문제였다!