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

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

프로그래머스

 이번 문제는 집마다의 배달 및 수거할 택배 상자 개수가 주어졌을 때, 최소 이동 거리를 구하는 문제이다. 처음에는 이 문제를 어떻게 풀어야 하나 도저히 감이 잡히지 않았었다. 하지만, 이번 문제는 생각보다 매우 간단했다.

 우선, 첫 번째 예제를 이용해 생각해보자. 우선, 배달할 때이다. 배달할 때의 상자 개수는 각각 1, 0, 3, 1, 2개이며 cap은 4이다.만약 (잠시 cap을 신경쓰지 말고) 첫 번째 배달을 갈 때 1번 집, 4번집을 가고 두 번째 배달을 갈 때 3번 집, 4번 집을 가는 등, 집을 무작위로 간다면 최소 거리를 구하기 힘들 것이다. 이러한 상황을 방지하기 위해, 한 번 배달을 갈 때는 가장 멀리 있는 집에서 cap을 꽉 채워 배달을 가는 것이 좋을 것이다. 다시 말해, 첫 번째 배달에서는 5번 집에 2개, 4번 집에 1개, 3번 집에 1개를 배달한다. 그리고 두 번째 배달에서는 3번 집에 2개, 1번 집에 1개를 배달한다. 그렇다면 첫 번째 배달에서는 5번 집에 가장 멀기 때문에 거리가 5이며 두 번째 배달에서는 같은 이유로 거리가 3일 것이다.

 수거할 때의 거리 역시 이와 같은 방식으로 구한다. 수거할 때의 상자 개수는 각각 0, 3, 0, 4, 0이므로 첫 번째 수거는 거리가 4이며 두 번째 수거의 거리는 2이다. 이제, 이 정보를 이용하여 최소 거리를 계산해야 한다. 우선, 첫 번째 배달+수거의 거리이다. 둘의 값은 각각 5와 4로 다르다. 하지만 첫 번째의 거리는 5 + 4 = 9가 아니다. 왜냐하면 결국 배달하러 5라는 거리를 간 후, 다시 5만큼 되돌아가야 하기 때문이다. 그렇기 때문에, 첫 번째 배달+수거의 거리는 5 + 5 = 10이다. 두 번째 배달+수거에서 배달의 거리는 3이고 수거의 거리는 2이다. 이 역시 같은 이유로 3 + 3 = 6이다. 그렇기 때문에 첫 번째 예시의 답은 10 + 6 = 16이다. 여기서 알 수 있는 사실은, 답은 각 순간의 배달/수거의 최대값x2의 합으로 계산된다는 사실이다. 만약 수거할 때의 거리가 더 길더라도 똑같은데, 왜냐하면 배달 가야 할 거리가 더 짧더라도 결국 수거하러 더 멀리 가야하기 때문이다.

 만약 배달이 다 끝났는데 수거할 상자가 남거나 그 반대의 경우도 있을 것이다. 이럴 경우는 남은 각 순간의 거리x2의 값을 답에 더해주면 된다. 2를 곱하는 이유는 결국 배달이든 수거든 왕복을 해야 하기 때문이다. 이를 바탕으로 구상한 절차는 다음과 같다.

1. cap을 꽉 채워서 배달/수거를 할 때의 최대 거리들을 구한다.
2. 배달/수거를 같이할 수 있을 때까지의 최대 거리들의 합을 구한다.
   1. 만약, 배달/수거를 따로 더 해야 한다면, 그 거리들만 따로 더한다.
3. 왕복이기 때문에 2를 곱한 값을 반환한다. (오고 가는 거리)

 

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

using namespace std;

// 주어진 정보에서 각 타임마다의 최대거리를 구하는 함수
vector<int> CheckDistances(int cap, vector<int> info)
{	
	// 스택을 이용하여 가장 먼 거리부터 구한다.
	stack<int> stk;

	vector<int> distances;	// 반환할 배열

	int curCap;				// 각 순간마다의 cap
	int maxDistance;		// 각 순간마다의 최대 거리

	// 1. 거리를 처음부터 탐색한다.
	for (int i = 0; i < info.size(); ++i)
	{	
		// i + 1 => 시작점에서 i번까지의 거리

		// 1-1. 만약 i번째에 배달/수거할 것이 있다면, 그 횟수만큼 거리를 스택에 push한다.
		// stk.top = n -> n이라는 거리에 상자가 있다는 뜻
		if (info[i] > 0)
		{
			while(info[i] > 0)
			{	
				stk.push(i + 1);
				--info[i];
			}
		}
	}

	curCap = cap;
	maxDistance = -1;
	
	// 스택에는 상자의 개수만큼 거리 정보가 담기는데
	// 스택이 비었다는 말은 모든 상자를 배달/수거했다는 뜻이다.
	// 그렇기 때문에 스택이 빌 때까지 반복한다.
	while(!stk.empty())
	{	
		int distance = stk.top();	// 현재 상자의 위치
		stk.pop();

		--curCap;	// 상자 하나 해결했기 때문에 1 감소

		// 만약 현재 상자의 거리가 기록된 거리보다 크다면 갱신한다.
		if (maxDistance < distance)
			maxDistance = distance;

		// 만약 허용치가 0이거나 상자가 없다면, 
		// 이번 순간의 최대 거리를 기록한다.
		if (curCap == 0 || stk.empty())
		{
			distances.push_back(maxDistance);

			curCap = cap;
			maxDistance = -1;
		}
	}
	
	return distances;
}

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

	// 1. cap을 꽉 채워서 배달/수거할 때의 최대 거리들을 구한다.
	vector<int> deliveryDistances = CheckDistances(cap, deliveries);
	vector<int> pickupDistances = CheckDistances(cap, pickups);

	// 2. 배달/수거를 공통적으로 할 수 있을 때까지의 최대 거리들의 합을 구한다.
	if (deliveryDistances.size() < pickupDistances.size())
	{
		int sameLastPoint = deliveryDistances.size();

		for (int i = 0; i < sameLastPoint; ++i)
			answer += max(deliveryDistances[i], pickupDistances[i]);

		// 2-1. 만약 배달/수거를 따로 더 해야한다면, 그 거리들만 따로 더해준다.
		for (int i = sameLastPoint; i < pickupDistances.size(); ++i)
			answer += pickupDistances[i];
	}
	else
	{
		int sameLastPoint = pickupDistances.size();

		for (int i = 0; i < sameLastPoint; ++i)
			answer += max(deliveryDistances[i], pickupDistances[i]);

		// 2-1. 만약 배달/수거를 따로 더 해야한다면, 그 거리들만 따로 더해준다.
		for (int i = sameLastPoint; i < deliveryDistances.size(); ++i)
			answer += deliveryDistances[i];
	}

	// 3. 왕복이기 때문에 2를 곱해준다.(오고 가는 거)
	return answer * 2;
}