문제 URL
https://school.programmers.co.kr/learn/courses/30/lessons/43238
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
[문제 설명]
입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 반환하는 문제이다.
[문제 풀이]
이진 탐색을 이용하여 푸는 문제이다.
이진 탐색 방법은 아래와 같다.
- 심사에 걸리는 최소 시간과 최대 시간의 중앙값을 구한다.
- 이 중앙값 시간동안 각각의 심사관들이 몇 명을 심사할 수 있는지 구하여 더한다.
- 만약, 중앙값 시간동안 심사한 인원이 n보다 크거나 같다면 최대 인원보다 많이 심사한 것이므로 최대 시간을 평균 -1로 변경해주고 answer을 평균으로 갱신한 뒤 다시 중앙값을 계산하여 탐색을 실시한다.
- 만약, 중앙값 시간동안 심사한 인원이 n보다 적다면 최소 시간을 평균 +1로 변경해주고 다시 다시 중앙값을 계산하여 탐색을 실시한다.
- 한 번 반복할 때마다 심사한 사람(human)을 초기화하며, 위 과정을 min값이 max값보다 크거나 같을 때까지 반복한다. => 반복문을 탈출하게 된다면 answer에 최소시간이 담기게 된다.
#include <vector>
#include <algorithm>
using namespace std;
long long solution(int n, vector<int> times) {
int time_size = times.size();
sort(times.begin(), times.end());
long long min_time = 1; // 가장 짧은 시간
long long max_time = (long long)times[time_size-1] * n; // 가장 오래 걸리는 시간
long long mid_time; // 중앙값
long long human = 0;
long long answer = max_time;
while(min_time <= max_time) { // 이분탐색
mid_time = (min_time + max_time) / 2;
for (auto t : times) // mid_time 동안 처리할 수 있는 사람의 수를 카운트
human += mid_time / t;
if (n <= human) {
answer = min(answer, mid_time);
max_time = mid_time - 1;
}
else // 시간이 부족
min_time = mid_time + 1;
human = 0;
}
return answer;
}
