프로그래머스 - 입국심사

입국심사 (2021. 07. 12) Entry Audit (Binary Search)

문제 및 풀이 주소

Programmers
Git Solution

문제 설명

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

입출력 설명

• 가장 첫 두 사람은 바로 심사를 받으러 갑니다.
• 7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.
• 10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.
• 14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.
• 20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

문제 해결

이슈 케이스

해당 문제에서 이분탐색을 사용해야하는 부분이 어디인가?에 대한곳을 찾을 수 없었다. 단순히 처음에는 Set으로 각각의 시간을 addAll하여 중복을 제거하고 마지막 n값을 get할 수 있으면 끝일줄 알았다. 하지만 역시나 테스트케이스 실패의 향연... 다시 처음으로 돌아와 이분진법을 사용해야 하는 부분을 찾기 시작했다.

문제의 주제가 이분탐색이므로, 어느 부분에는 반드시 이분탐색을 적용해야한다. 이분탐색에서 가장 중요한 요소는 정렬이 필수로 되어 있어야 한다. 주어지는 배열 times는 정렬이 되어 있지 않으므로 제외해야하고, 그렇다면 남은것은 시간의 범위이다. ( 실제로는 엄청난 삽질을 하였다 )

심사자가 받을 수 있는 가장 빠른 범위의 시간과, 가장 느린 범위의 시간을 구하는것으로 먼저 고민하였다. 심사관마다 시간이 주어지지만, 문제에서 중복이 안된다고 하지 않았으니까 최소의 시간은 times의 최소값, 최대의 시간은 times의 최대값으로 지정하면 될것 같고, times에서 모든 n값이 최소값과 최대값으로만 이루어진 시간을 구하기로 하였다.

long divide = (long) Math.ceil((double) n / times.length);
//정렬
Arrays.sort(times);
// 최소값
long min = times[0] * divide;
// 최대값
long max = times[times.length - 1] * divide ;

스트림 람다를 사용하면, min과 max에 각각 적용해야 하므로, times를 Sort하는 방향으로 생각하였다.

---

이후의 모든 시도는 많은 시간을 들였음에도 전부다 실패하였다... 특히나, 이분탐색을 하는 코드를 긁어와서 재귀의 방식과 while로 하는 방식 둘다 적용을 하였는데 실패했다.

해결 케이스

어떻게 해결해야 할까? 하다가 결국 풀이하는 방식을 보기로 했는데, 특정 공식을 알수 없으면 문제를 해결할 수 없는것 같다.. 탐색하면서 매번 일일이 처음부터 n값이 될때까지 모든걸 계산해야 하나? 했더니 다음과 같은 공식이 있었다.

for(int time : times){
    sum += int(((low+high) / 2) / time)
}

모든 사람을 계산하지 않고 해당 공식하나만으로 심사받는 사람의 수를 구할 수 있다... ( 너무 허무했다..)
하지만 바로 성공할 수는 없었는데 이분탐색 예제를 그대로 적용하였더니 원하는 수가 나오지 않고 전체 탐색을 하면 다른값이 나오기 시작했다.

if(sum == key){
    return mid
}else if(sum > key) {
    high = mid - 1;
} else {
    low = mid + 1;
}

key값이 심사받은 사람수 인데 구글링해온 이분탐색 코드는 원하는 값을 찾았을 경우, 바로 return 하는 코드였다. 해당 코드를 그대로 적용하였는데, 당연하게도 실패하였다. 실패원인은 다음과 같다.

특정값에서 sum == key의 조건이 이루어지지만, 그다음값도, 그다다음값도 sum == key의 값이 되는 조건들이 있다.

여러 sum ==key의 조건 때문에 처음에는 times각각의 값에서 배수값이 필요하지 않을까 생각했는데, 실제 코드를 보니 그럴필요가 없다는것을 알았다. ( 애초에 저렇게 나누어서 저장하면 최소값이 배열값으로 되는것 같다. )

if(sum < key) {
    low = mid + 1;
} else {
high = mid - 1;
    result = mid;
}

sum == key의 조건이 사라지고 부등호의 방향이 바뀌어서 처리되었다.
부등호의 방향은 상관없을 줄알았는데 해당 표시가 바뀜에 따라 값이 달라지게 되었다.

테스트 결과

테스트 번호	통과여부	메모리 및 시간	테스트 번호	통과여부	메모리 및 시간
테스트 1	통과	(0.72ms, 52MB)	테스트 6	통과	(109.47ms, 60MB)
테스트 2	통과	(0.60ms, 53MB)	테스트 7	통과	(100.97ms, 60.5MB)
테스트 3	통과	(2.64ms, 55.4MB)	테스트 8	통과	(138.49ms, 60.7MB)
테스트 4	통과	(105.26ms, 59.6MB)	테스트 9	통과	(0.74ms, 52.4MB)
테스트 5	통과	(100.82ms, 58.1MB)

후기

해당 문제는 좀... 사람수를 구하는 공식을 모르면 절대로 풀수 없는 문제 같았다. 시간도 많이 걸렸거니와 저 문제의 공식을 혼자서 스스로 도출한 것이 아니기 때문에 찝찝함이 많은 문제였다. 실제 정답코드는 저리 짧은데..