[프로그래머스] 택배 배달과 수거

1. 첫 번째 접근

• 배달하는 양은 항상 최대값 만큼 배달하고 수거한다.
• 배달과 수거는 남아있는 가장 먼곳부터 진행한다.

1. 배달과 수거할 집들 중 가장 먼곳의 집을 왕복한 거리를 answer에 더한다.
2. 배달한 물량만큼 줄여준다.
3. 수거한 물량도 줄여준다.

public long solution(int cap, int n, int[] deliveries, int[] pickups)
{
	long answer = 0;
	int deliverIndex = deliveries.Length;
	int pickupIndex = pickups.Length;

	while (deliverIndex - 1 > 0 || pickupIndex - 1 > 0)
	{
		int deliverCount = cap;
		int pickupCount = cap;
		int maxDistance = Math.Max(deliverIndex, pickupIndex);
		answer += maxDistance * 2;
		for (int i = deliverIndex - 1; i > 0; i--)
		{
			deliveries[i] -= deliverCount;
			if (deliveries[i] > 0)
			{
				break;
			}
			deliverCount = -deliveries[i];
			deliverIndex--;
		}
		for (int i = pickupIndex - 1; i > 0; i--)
		{
			pickups[i] -= pickupCount;
			if (pickups[i] > 0)
				break;
			pickupCount = pickupCount - pickups[i];
			pickupIndex--;
		}
	}
	return answer;
}

결과 : 시간초과
원인 : 실제 배달과정을 하나하나 더하는 횟수가 너무 많음 (짐칸이 1개인데 50개를 배달해야하면 50번 왔다리 갔다리 * 100,000정도 해버리면 너무 많음)

2. 두 번째 접근

• 하나하나 더하거나 빼지않고 배달한 양을 누적시켜서 계산하기로 했다. (어차피 갈 때 최대로 배달하고 올때 최대로 수거하기 때문에 가는 동안 이미 배달을 했다는 느낌)

1. 가장 멋곳의 배달량과 수거량중 큰값을 선택한다.
2. 같은곳에 배달을 몇번 반복해야하는지 구한다.
3. 최대 재적량만큼 배달과 수거를 진행했다고 생각하고 배달한 누적값과 수거한 누적값을 저장한다.
4. 시작할 때 누적값만큼 빼서 이미 배달한 곳인지 확인한다.

public long solution(int cap, int n, int[] deliveries, int[] pickups)
{
	long answer = 0;
	int deliverCount = 0;
	int pickupCount = 0;
	while (n > 0)
	{
		// 4. 시작할 때 누적값만큼 빼서 이미 배달한 곳인지 확인한다.
		deliveries[n - 1] -= deliverCount;
		deliverCount = -deliveries[n - 1];
		pickups[n - 1] -= pickupCount;
		pickupCount = -pickups[n - 1];
		if (deliveries[n-1] <= 0 && pickups[n-1] <= 0)
		{
			n--;
			continue;
		}
		// 1. 가장 멋곳의 배달량과 수거량중 큰값을 선택한다.
		int maxCount = Math.Max(deliveries[n-1], pickups[n-1]);
		// 2. 같은곳에 배달을 몇번 반복해야하는지 구한다.
		int repeatCount = maxCount / cap;
		if (maxCount % cap > 0)
			repeatCount++;
		// 3. 최대 재적량만큼 배달과 수거를 진행했다고 생각하고 배달한 누적값과 수거한 누적값을 저장한다. 
		deliverCount = repeatCount * cap - deliveries[n - 1];
		pickupCount = repeatCount * cap - pickups[n - 1];
		answer += n * repeatCount * 2;
		n--;
	}
	return answer;
}

결과 : 성공 while문을 n번만 돌아서시간도 대폭 줄었다.