[Java] 프로그래머스 level3 입국심사

https://school.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명 이하입니다.

 

문제 접근

이번 문제는 이분 탐색 문제이다. 이분 탐색 문제 유형 중에는 매개변수 탐색(PrametricSearch)가 있는데 이번 문제가 매개변수 탐색 문제이다. 구현은 매우 간단하다. 

 

calculate method

public static long calculate(long check){
        long sum = 0;
        for(int i = 0; i < size; i++){
            sum += check / time[i];
        }
        return sum;
}

calculate 메서드는 매개변수로 시간이 들어오면 입국 심사관들이 처리 가능한 사람의 숫자를 구하고 해당 숫자를 sum에 누적한다.

그리고 해당 sum을 반환한다.

다시 말해서 해당 시간(check)에 최대 몇 명을 처리할 수 있는지 계산하는 메서드이다.

 

BinarySearch (lower_bound)

 while(start < end){   // lower_bound
      long mid = (start + end) / 2;
      long count = calculate(mid);
      if(n <= count){
          end = mid;
      }
      else start = mid + 1;
  }

 

lower_bound의 의미는 찾고자 하는 값 이상이 처음 등장하는 걸 구한다는 뜻이다.

우리는 최소한의 시간으로 입국하는 모든 사람을 처리하고 싶으니까 calculate한 결과가 처음으로 n명 이상인 시간대를 찾는게 목표이다. 그래서 lower_bound를 사용한다. 

 

lower_bound는 어떻게 하는가?

제일 많이 실수하고 까먹는 부분이다. 다음 while 문에서 돌아갈 end와 start의 설정을 잘못하면 무한 루프에 빠지기도 하고 잘못된 데이터가 나온다.

 

자 먼저 n <= count를 보자 count = calculate 반환값 

만약 n 보다 반환값이 크다면 처음 등장하는 값을 구하고 싶은 거니 이후의 값들은 탐색할 필요가 없다. 

그래서 end를 mid로 설정한다. 

그럼 else의 조건은 자연스럽게 n > count 의 조건을 만족하는 경우에 동작한다. 

처리해야 하는 사람이 count보다 많으면 무조건 시간을 늘려야 하니까 start를 mid + 1로 한다. 

그 이유는 mid가 n > count 조건이기 때문에 시간을 늘리는 거다.

이렇게 계속 탐색 범위를 줄여 나가면 start는 n 이상을 갖는 최초의 값이 된다. 

 

[참고] 반대로 upper_bound는 if else 조건을 조금만 수정하고 end를 반환하면 된다. 

 

77점 코드

import java.util.*;
class Solution {
    static long answer;
    static int [] time;
    static int size;
    public long solution(int n, int[] times) {
        size = times.length;
        time = Arrays.copyOf(times, size);
        long start = 0;
        long end = Long.MAX_VALUE;    
        while(start < end){   // lower_bound
            long mid = (start + end) / 2;
            long count = calculate(mid);
            if(n <= count){
                end = mid;
            }
            else start = mid + 1;
        }
        return start;
    }
    public static long calculate(long check){
        long sum = 0;
        for(int i = 0; i < size; i++){
            sum += check / time[i];
        }
        return sum;
    }
}

 

풀이가 완벽하다고 생각했는데 역시 오만이었다. 

어디서 틀리는걸까? 

결국 풀이의 핵심은 2개다. calculate method / binarysearch 

 

만약 입국 심사를 기다리는 사람이 1000,000,000 이고 심사관이 100,000인데 처리하는데 걸리는 시간이 모두가 1분이라는 case를 생각해봤다. 
그럼 맨 처음 Long.MAX_VALUE가 calulate로 들어가면 음수 값이 나온다

Long.MAX_VALUE * 100,000 = long 범위를 넘어선다. 

문제의 정답이 Long 범위니까 최댓값을 넣은 건데 좀 줄여야 한다. 

대충 100으로 나누어 주었다.

통과 코드

import java.util.*;

class Solution {
    static long answer;
    static int [] time;
    static int size;
    public long solution(int n, int[] times) {
        size = times.length;
        time = Arrays.copyOf(times, size);
        long start = 0;
        long end = Long.MAX_VALUE / 100;    
        while(start < end){   // lower_bound
            long mid = (start + end) / 2;
            long count = calculate(mid);
            if(n <= count){
                end = mid;
            }
            else start = mid + 1;
        }
        return start;
    }
    public static long calculate(long check){
        long sum = 0;
        for(int i = 0; i < size; i++){
            sum += check / time[i];
        }
        System.out.println(check);
        System.out.println(sum);
        return sum;
    }
}

 

 

점점 코테에 익숙해지면서 구현은 금방 하지만 반례를 찾는 데에 시간 소비가 훨씬 많아지는 것 같다. 

현업 개발자들은 시간투자를 시스템 개발은 30% 테스트 코드를 작성하는데 70%를 사용한다는데 뭔가 점점 이해가 되는듯하다

 

감사합니다!! :)