[Programmers] 입국심사

김민석·2021년 12월 10일
0

프로그래머스

목록 보기
25/30

모든 사람이 심사를 받는데 걸리는 최소 시간을 구하는 문제이다.

문제해결 전략
처음에는 사람 한명한명을 최소 시간을 갖고 있는 심사관에게 배치하려 하였다.

하지만 사람의 수가 최대 10억명이고 심사관의 수가 최대 10만명이므로 굉장히 큰 반복횟수가 필요하므로 한명씩 하면 안됐다.

우선 이 문제가 이분탐색 카테고리 이므로 이분탐색을 어떻게 적용할 수 있을까 생각해 보았다.

이분탐색이란 정렬된 데이터에서 특정 값을 찾는 탐색 방법이다.

이분탐색을 적용하기 위해서는 찾아야 하는 값과 정렬된 데이터가 존재해야 한다.

우선 찾아야 할 값을 어떤것으로 선정해야 하는지 고민해 보았다.

문제에서 요구하는 답은 모든 사람을 다 처리할 수 있는 최소 시간이지만 알려진 값은 사람의 수 뿐이다.

따라서 특정 시간동안 모든 사람을 처리할 수 있는지 확인하여야 한다. 즉, 현재 확인하고자 하는 시간이 t라면 t분 동안 각 심사관이 처리할 수 있는 사람수의 총합이 비교 대상이 되고, 타겟값은 처리해야 할 사람의 수가 된다.

다음으로 정렬된 데이터가 무엇일까 생각해 본다.

시간값을 비교하므로 정렬된 데이터 역시 시간과 관련된 값임을 알 수 있다.

시간의 최솟값을 1으로 한다.
최댓값은 가장 느린 심사관이 다 맡는 경우 이므로 가장느린심사시간x사람 수 가 된다.

이제 0부터 최대값 까지 이분탐색을 진행한다.

정리하자면 다음과 같다.

  1. 초기값 : 최소 시간 1, 최대 시간 가장느린심사시간x사람수
  2. 중앙값 계산 (mid)
  3. 심사관 별 mid 시간 동안 처리할 수 있는 사람의 총합처리해야 할 사람의 수 값 비교
    3.1 처리해야 할 사람의 수가 더 많으면 최소값을 mid+1로 해줌
    3.2 처리해야 할 사람의 수가 더 적으면 최대값을 mid-1로 해줌
    3.3 처리해야 할 사람의 수와 같더라도 그 값들 중에서도 최소값을 구해야 하므로 최대값을 mid-1로 하여 계속 진행
  4. 위 과정을 최소값이 최대값보다 커지기 전까지 반복

느낀점
이분탐색 개념은 알고 있었는데 이런식의 문제로 나오니까 어떻게 적용해야 하는지 막막했다.

좀 더 문제를 많이 풀어보며 알고있는 알고리즘을 어떻게 적용할 수 있을까 좀 더 고민해봐야 겠다.

코드

#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 right = (long long)times[times.size()-1]*n;
    long long left = 1;
    long long mid;
    while(left <= right){
        mid = (right + left)/2;
        
        long long cnt = 0;
        for(int i=0;i<times.size();i++){
            cnt += mid / times[i];
        }
        
        if(cnt < n){
            left = mid + 1;
        }else{
            if(mid <= right){
                answer = mid;
            }
            right = mid - 1;
        }
    }
    
    return answer;
}

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

profile
김민석의 학습 정리 블로그

0개의 댓글