[프로그래머스/C++] 입국심사 - 이분탐색

• 입국심사

문제 설명

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

입출력 예

 

n	times	return
6	[7, 10]	28

 

입출력 예 설명

가장 첫 두 사람은 바로 심사를 받으러 갑니다.

7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.

10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.

14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.

20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

---

해당 문제는 이분탐색을 이용하는 문제로써, 심사를 받는 최소시간과 최대시간을 low, high 값으로 잡으면 된다.

먼저, 심사를 받는 최소 시간은 문제의 제한사항에 따라 1분이다. (심사시간은 1분이상 1,000,000,000분 이하)

그렇다면 최대시간은 현재 vector로 주어지는 심사 시간의 최댓값 * n명을 곱한 값일 것이다.

7분 심사와 10분 심사가 존재할 때 6명 모두가 10분 심사를 받으면 60분으로 최대 심사 시간이 나오기 때문이다.

 

따라서 low = 1, high = times.back()(오름차순 정렬하여 vector의 최댓값) * n(사람수); 으로 이분탐색의 시작과 끝을 초기화 해주었다.

 

이분탐색은 꼭 정렬된 배열에서만 수행되어야 한다는 점을 잊지말자.

 

이후, low <= high 인 경우동안만 while문을 반복하고, 이분탐색의 원칙대로 mid 값을 구하면서 해당 mid 시간 안에 심사위원들이 처리할 수 있는 사람 수를 구하였다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

long long solution(int n, vector<int> times) {
	long long answer = 0;
	long long low = 1;
	long long high = (long long)times.back() * n;

	sort(times.begin(), times.end());

	while (low <= high)
	{
		long long mid = (low + high) / 2;
		long long temp = 0;

		for (int i = 0; i < times.size(); i++)
			temp += (mid / times[i]);

		if (temp >= n)
		{
			high = mid - 1;
			answer = mid;
		}
		else
			low = mid + 1;
	}
	return answer;
}

 

times 벡터만큼 for문을 돌면서 mid값 / 심사시간을 나누어 각 심사위원이 몇명의 사람까지 심사할 수 있는지를 구하고, temp 변수에 인원수를 더하였다.

 

이후, 최종 temp 변수의 인원수가 매개변수 n명보다 크다면 더 넉넉하게 검사한 것이므로, mid보다 더 작은 시간동안 심사를 보도록 시간을 줄이고, 

temp 변수가 n보다 작다면 심사 시간이 부족한 것이므로 mid보다 더 큰 시간동안 심사를 보도록 시간을 늘여주었다.

 

또한 이 문제의 중요 키워드는 자료형의 범위였다. 

문제의 제한사항의 인원이 1명 이상 1,000,000,000명 이고, 심사 시간도 1분 이상, 1,000,000,000분 이하인만큼 수치가 크기때문에 long long 자료형을 주의깊게 사용해야 했다.

 

단순 low, high, mid, temp 변수만 long long 형으로 설정하면 되는것이 아니라, high 값을 계산할때의 times.back() * n 같은 연산에서도 따로 long long 형변환을 진행해야 연산자 오버로딩이 나타나지 않고 모든 테스트 케이스가 성공될 수 있었다.