프로그래머스 - 입국심사 (C++)

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

프로그래머스

 이번 문제는 입국 심사에 걸리는 시간들과 입국 심사를 기다리는 인원 수가 주어졌을 때, 모든 인원이 입국 심사를 받기 위한 최소 시간을 구하는 문제이다. 이 문제가 이분 탐색으로 분류되어 있는데, 처음에는 이 문제를 도대체 어떻게 이분 탐색으로 풀어야 하는지 이해가 가지 않았다. 왜냐하면 평소에 알고 있던 이분 탐색은 정렬되어 있는 배열 속에서 원하는 것을 찾는 알고리즘이었기 때문이다. 그렇지만 계속해서 생각해 본 결과, 알게 되었다. 이 문제에서 이분 탐색할 것은 바로 시간이다. 1부터 어떤 최대 입국 심사 시간까지 정렬되어 있는 시간에 이분 탐색을 이용하면 되는 것이었다. 더 자세히 말하자면, 가장 긴 입국 심사 시간은 가장 시간이 긴 심사대에 모든 사람이 심사받는 경우일 것이다. 그리고 이분 탐색에는 left와 right의 값이 필요한데, left의 값은 1로, right의 값은 가장 긴 입국 심사 시간으로 둔다. 그리고 이분 탐색을 진행하면서 저 두 값의 중간값(각 경우의 입국 심사 시간)에 해당하는 시간 동안 각 심사대에서 몇 명 심사할 수 있는지를 계산하고 이를 이용해 이분 탐색을 진행한다. 

1. 편의를 위해 모든 값들을 long long형으로 바꾼다. 동시에 심사 받는 시간 중, 가장 긴 심사 시간을 찾는다.
2. 이진 탐색을 위한 변수를 설정한다. left의 값은 1(심사하는 데 있어서 최소 1분은 걸리기 때문), right의 값은 심사 최대 시간 x 사람의 수이다. (최악의 경우)
3. 이진 탐색을 시작한다.
   1. 중간값이 각 경우의 총 심사 시간이며, 각 심사대마다 현재 주어진 시간동안 몇 명을 심사할 수 있는지를 계산, 총합을 구한다. 
   2. 만약 모든 심사된 인원이 문제에서 주어진 사람의 수보다 작다면 시간이 부족하다는 뜻이므로 left의 값을 증가시킨다.
   3. 만약 총 심사된 인원의 수가 주어진 사람의 수와 같거나 크다면 시간이 충분하다는 뜻이므로 답에 시간을 저장한 후, right의 값을 줄인다.

 

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

using namespace std;

long long maxCheckTime;
long long peopleNum;
vector<long long> checkTimes;

long long solution(int n, vector<int> times)
{
	// 1. 편의를 위해 모든 값들을 long long형으로 바꾼다.
	// 동시에 심사 받는 시간 중, 가장 긴 심사 시간을 찾는다.
	long long answer = 0;
	
	peopleNum = n;

	for (int i = 0; i < times.size(); ++i)	
	{
		checkTimes.push_back(times[i]);
		maxCheckTime = max(maxCheckTime, checkTimes.back());
	}

	// 2. 이진 탐색을 위한 변수를 설정한다.
	// left의 값은 1(심사하는 데 있어서 최소 1분은 걸리기 때문)
	// right의 값은 심사 최대 시간 x 사람의 수이다. (최악의 경우))
	long long leftTimeVal = 1;
	long long rightTimeVal = maxCheckTime * peopleNum;

	// 3. 이진 탐색을 시작한다.
	while(leftTimeVal <= rightTimeVal)
	{
		long long midTimeVal = (leftTimeVal + rightTimeVal) / 2;

		long long passPeopleNum = 0;

		// 3-1. 중간값이 이번 경우의 총 심사 시간이며
		// 각 심사대마다 현재 주어진 시간동안 몇 명을 심사할 수 있는지를 계산, 총합을 구한다.
		for (int i = 0; i < checkTimes.size(); ++i)
			passPeopleNum += (midTimeVal / checkTimes[i]);

		// 3-2. 만약 모든 심사된 인원이 문제에서 주어진 사람의 수보다 작다면
		// 시간이 부족하다는 뜻이므로 left의 값을 증가시킨다.
		if (passPeopleNum < peopleNum)
			leftTimeVal = midTimeVal + 1;
		else
		{
			// 3-3. 만약 총 심사된 인원의 수가 주어지 사람의 수와 같거나 크다면
			// 시간이 충분하다는 뜻이므로 답에 시간을 저장한 후, right의 값을 줄인다.
			answer = midTimeVal;
			rightTimeVal = midTimeVal - 1;
		}
	}

	return answer;
}