[프로그래머스/C++] 입국심사

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/43238

코딩테스트 연습 - 입국심사

 

풀이

 

이 문제는 이분 탐색(Binary Search)을 활용하여 푸는 문제이다. 이분 탐색을 통해 예상 답을 먼저 구하고 그 답이 진짜 답이 맞는지 체크 후 다시 다시 새로운 답을 구하면 된다.

sort(times.begin(), times.end());   // times를 오름차순으로 정렬
long long lt = times[0], rt = (long long)n * times[0], mid, num;

일단 times를 오름차순으로 정렬해준다. 굳이 정렬이 필요한 것은 아니지만 lt와 rt값 차이를 줄여주기 위해 정렬을 해줬다. lt는 올 수 있는 가장 작은 수 times[0]으로 초기화해주고 rt는 올 수 있는 큰 수 중 가장 작은 수를 넣어주었다. 여기서 주의할 점은 n과 times[0]이 둘 다 int형 이기 때문에 꼭 둘 중 하나는 long long으로 형 변환을 해줘야 한다. 그렇지 않으면 3,5,7,8번이 오답으로 나온다. (범위 실수를 많이 하는데 주의해서 봐야 할 것 같다.) mid는 lt와 rt의 중앙값, 즉 예상 답이고 num은 답을 체크해 주기 위한 변수이다.

while(lt <= rt){
    mid = (lt + rt) / 2;
    num = 0;
    for(int i: times){
        num += (mid / i);
    }
        
    if(num >= n) {
        rt = mid - 1;
        answer = mid;
    }
    else lt = mid + 1;
}

그다음 while문을 돌리면서 이분 탐색을 해준다. mid값을 구하고 num을 매번 새로 구해줘야 하기 때문에 0으로 초기화한다. num은 만약 mid가 답이라면 총 몇 사람이 심사를 받을 수 있는가를 구해서 저장해 줄 변수이다. for문을 times의 개수만큼 돌리면서 mid / i의 몫을 더해주면 mid시간만큼 심사를 받을 수 있는 사람의 최댓값이 나온다.

 

이 값을 가지고 탐색을 하는데 만약 num이 n보다 크거나 같다면 mid보다 더 작은 값으로도 n명의 심사를 할 수 있다는 뜻이다. 우리는 최솟값을 구해야 하기 때문에 rt를 mid - 1로 줄여서 다시 구하고 이 수가 답이 될 수도 있으므로 answer에는 mid를 넣어준다. 그리고 만약 num이 n 보다 작다면 더 큰 mid가 필요하다는 뜻이므로 lt를 mid + 1로 바꿔준다.

 

이렇게 while문을 돌면서 lt가 rt보다 커지면 answer에는 올 수 있는 가장 최소의 mid값이 들어가 있게 된다.

 

전체 코드

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

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    
    sort(times.begin(), times.end());
    long long lt = times[0], rt = n * (long long)times[0], mid, num;
    
    while(lt <= rt){
        mid = (lt + rt) / 2;
        num = 0;
        for(int i: times){
            num += (mid / i);
        }
        
        if(num >= n) {
            rt = mid - 1;
            answer = mid;
        }
        else lt = mid + 1;
    }
    return answer;
}