C# [프로그래머스] Lv.3 입국심사

 

 

 

 

 

 

 

 

문제 설명

 

입국 심사를 기다리는 사람들이 입국 심사에 걸리는 최소한의 시간을 계산해야 하는 문제다.

 

입국 심사를 기다리는 사람은 최대 10억명이고, 심사관의 숫자는 10만명 이하, 그리고 심사관 한명이 입국 심사에 걸리는 시간은 최대 10억분까지도 걸릴 수 있는 제한사항이 주어진다.

 

얼핏 봐도 최적화가 중요한 문제이고 역시나 완전 탐색으로 먼저 풀어보니 1분마다 시간을 계산해서는 시간복잡도에서 높은 확률로 통과하지 못하는 문제였다.

 

 

최적화를 어떻게 시킬까 고민하다가 이분 탐색(이진 탐색) 기법을 사용해서 중간 시간 값을 체크해서 경우의 수를 줄여나가는 방법으로 접근했고 다음과 같은 방식으로 풀어보았다.

 

 

 

해당 코드

public static long solution(int n, int[] times)
{
	// left는 가능한 최소 시간을 설정 (최소 1분)
	long left = 1;

	// right는 가능한 최대 시간을 설정 (가장 느린 심사관이 모든 사람을 처리하는 시간)
	long right = (long)times.Max() * n;

	// 정답을 저장할 변수, 일단 최대 시간으로 설정
	long answer = right;

	// 이분 탐색을 시작 (left가 right보다 작거나 같을 때까지 반복)
	while (left <= right)
	{
		// 중간값(mid)을 계산 (left와 right의 중간값)
		long mid = (left + right) / 2;

		// mid 시간 동안 처리할 수 있는 총 사람 수를 계산할 변수 total
		long total = 0;
	
		// 각 심사관이 mid 시간 동안 처리할 수 있는 사람 수를 계산하여 total에 더함
		for (int i = 0; i < times.Length; i++)
		{
			// 심사관이 mid 시간 동안 처리할 수 있는 사람 수는 mid를 심사 시간으로 나눈 몫
			total += mid / times[i];
		}

		// 총 처리한 사람 수가 n명 이상이면, 더 적은 시간으로도 가능할 수 있음
		if (total >= n)
		{
			// 가능한 최소 시간을 찾기 위해 answer를 현재 mid로 업데이트
			answer = mid;

			// 더 적은 시간으로도 가능할 수 있으므로, right 값을 mid - 1로 줄임
			right = mid - 1;
		}
		else
		{
			// 총 처리한 사람 수가 n명보다 적으면 시간이 더 필요하므로, left 값을 mid + 1로 늘림
			left = mid + 1;
		}
	}

    // 이분 탐색이 끝나면 answer에 최소 시간이 저장되어 있으므로 반환
    return answer;
}

 

 

 

 

풀이 방법

**탐색할 숫자가 상당히 크기 때문에 자료형은 long으로 하는것이 바람직하다.

 

 

이분 탐색의 핵심은 left(최소 값)와 right(최대 값)을 정한 뒤에 left와 right 사이에 위치할 middle값을 선정해 주어야 한다.

 

left와 right 값을 반복문을 돌리면서 원하는 최적화 된 값을 구할 때 까지 반복하고, 반복문 내에서는 특정 조건에 따라서 left와 right의 값을 증감시켜주면서 원하는 값을 탐색시켜 나간다.

 

middle 기준값 없이 left와 right를 하나씩 증감시킨다면 너무 많은 시간이 걸리므로 적절한 기준에 따라서 middle 값을 선정하는 것 역시 중요하다.

 

 

 

 

 

위 문제의 경우에는 left(최소 값), 즉 심사관의 심사하는데 걸리는 최소한의 시간을 1분이라고 가정하고 right는 각 심사관 마다 걸리는 시간 중 최대 값을 심사관 숫자 만큼 곱해준다. (long right = (long)times.Max() * n;) 

 

left 와 right 를 결정 했다면 이제 반복문을 돌리면서 각 조건에 따라 원하는 시간이 나올때 까지 계산을 해보자.

 

mid 값은 우선 중간값으로 선정한다. (long mid = (left + right) / 2;) 

 

total 값도 만들어주고 total은 각 심사관이 우리가 선정한 mid 시간에 최대 몇명을 상대할 수 있는지의 몫으로 선정해 준다.

 

이때 나오는 몫의 숫자, 즉 심사관이 처리할 수 있는 사람의 수가 n명보다 크다면 더 적은 시간으로 심사를 진행할 수 있다는 말이므로 answer 에 현재의 mid 값을 넣어준 다음 right의 시간을 줄여준다.

 

n보다 작은 경우에는 시간이 모자란 경우이기 때문에 left 값을 mid 값보다 늘려준다.

 

 

 

 

while문은  (left <= right) 즉 mid 값을 기준으로 범위를 줄여나가며

left 와 right가 제일 가까워진 시간, 즉 최적화된 시간이 나올때 까지 위 조건을 탐색하며 반복된다.

 

left < right의 경우에는 left와 right가 같아진 마지막 시간을 검사하지 않기 때문에 마지막 반복까지 검사하기 위해서는 

left <= right로 검사해 주는것이 안전하다.

 

 

해당 반복과 검사가 끝나면 answer에는 심사관들이 사람들을 심사하는 최소 시간(최적 시간)이 담기고 해당 값을 반환하게 된다.