프로그래머스 - 입국심사(Level 3)/Wanna Be 컴잘알

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

코딩테스트 연습 - 입국심사 | 프로그래머스

-문제-

 

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

 

-접근-

 

1. 입국심사 문제와 유사한 문제가 ACM ICPC에 나갔을 때도 나왔었는데, 입국심사를 하는데 가장 오래걸리는 시간을 High로 잡고 이분탐색을 진행해줍니다. 

위의 예시로 나온 경우는  최대 오래 걸리는시간은 6x10 = 60분입니다. mid는 30이 되므로 30분 기준 각 심사관들이 몇명을 처리할 수있는지 체크합니다. 30/7 = 4, 30/10 = 3  따라서 30분 동안 두 심사관은 7명의 입국자를 처리 할 수 있습니다. 주어진 n은 6이므로 1명을 더 처리하는 것을 불필요하고 시간이 더 오래걸리는 행위이므로 High = mid-1로 조정을 합니다. 이와 같은 방법으로 계속하여 이분탐색을 한다면 결과를 도출해 낼 수 있습니다.

 

2. 단 주의해야할 점은 n을 성립하는 최소값을 계속 저장해야한다는 점이다.  예를들면 mid=29초일경우에 똑같이 n은 6이 나온다. 그렇기 때문에 n ==cnt가 나온다고 바로 종료하면안되고, 조건이 성립하는 mid의 최소값을 기억해야한다. 

 

3. long long을 unsigned long long으로 처리해 준 이유는 오버플로우 발생방지인데, long long으로 할 때 테스트8에서 실패가 떴다.

long long의 범위는 약 -9,000,000,000,000,000,000~9,000,000,000,000,000,000이고 문제 조건에서 high로 가장 크게 나오는 경우는 1,000,000,000,000,000,000일 텐데, 그 경우 long long 범위를 초과하지 않을텐데 unsingend로 바꾸니 통과하였다. 아마 테스트로 주어진 값에 0이 하나 더 붙지 않았을까 싶다.

->테스트케이스 8번 틀리스는 분은 unsigned로 바꿔보시길

 

-코드-

 

Python

def binarySearch(left, right, times, n):
    cnt=0
    answer = -1
    while left <= right:
        mid = int((left+right)/2)
        cnt = 0
        for time in times:
            cnt += int(mid/time)

        if cnt >= n: 
            if answer == -1:
                answer = mid
            else:
                answer = min(answer,mid)
            right = mid-1
        elif cnt < n: left = mid+1
            
    return answer

def solution(n, times):
    times.sort()
    left = 0
    right = times[-1]*n
    answer = binarySearch(left, right, times, n)
    print(answer)
    return answer

solution(6,[7,10])

C++

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;


unsigned long long solution(int n, vector<int> times) {
	unsigned long long answer = 0;
	sort(times.begin(), times.end());

	unsigned long long low = 1;
	unsigned long long high = times[times.size() - 1] * n;

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

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

		if (cnt >= n) {
			if (answer == 0)
				answer = mid;
			else
				answer = min(answer, mid);
			high = mid - 1;
		}
		else {
			low = mid + 1;
		}
	}

	return answer;
}