[Java] 프로그래머스 - 입국심사 (3단계) *다시풀기

코딩 테스트 풀이 체크리스트
2시간 내에 풀었는가?	X
본인의 실력으로 풀었는가?	X

 

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

 

 

 

 

 

import java.util.*;

class Solution {
    
    long answer = Long.MAX_VALUE;
    
    public long solution(int n, int[] times) {
        
        Arrays.sort(times);
        
        long longTime = times[times.length-1];
        long maxTime = (long) longTime * n;
        
        func(n, times, 0, maxTime);
        
        return answer;
    }
    
    public void func(int n, int[] times, long start, long end) {
        long mid = (start + end) / 2;
        
        if (start < end) {
            long temp = 0;
            
            for (int i = 0; i < times.length; i++) {
                temp += mid / times[i];
            }
            
            if (temp == n) answer = Math.min(answer, mid);
            
            if (temp >= n) {
                func(n, times, start, mid);
            } else {
                func(n, times, mid + 1, end);
            }
        } else if (start == end) {
            answer = Math.min(answer, mid);
        }
    }
}

 

테스트 1 〉	통과 (0.57ms, 80.7MB)
테스트 2 〉	통과 (0.45ms, 77.1MB)
테스트 3 〉	통과 (1.68ms, 67.1MB)
테스트 4 〉	통과 (94.10ms, 96.1MB)
테스트 5 〉	통과 (90.28ms, 88MB)
테스트 6 〉	통과 (85.66ms, 94.3MB)
테스트 7 〉	통과 (90.17ms, 102MB)
테스트 8 〉	통과 (111.30ms, 83.7MB)
테스트 9 〉	통과 (0.42ms, 80.2MB)

 

 

 

 

 

이분탐색은 무엇이냐 하면...

예를 들어서 아래와 같이 정렬이 되어 있는 배열이 있다고 하자

 

1

2

3

4

5

6

7

8

9

10

 

 

 

이 때 숫자 3을 추가하고, 정렬을 하려고 하는데, 숫자가 적으면 그냥 앞에서부터 차근차근 하면 되는데

만약 이 숫자가 기하급수적으로 늘어날 경우와 숫자를 하나만 정렬하는게 아니고 추가할 때마다 정렬을 해야한다면

매번 정렬하는게 쉽지 않을 것이다.

그 때 필요한 것이 이분탐색인데, 이것은 정렬된 배열의 중간의 값을 기준으로 숫자가 작거나 같냐 크냐를 비교한 후에

작거나 같으면 왼쪽으로 다시 비교하고, 크면 오른쪽으로만 다시 비교하여 절반으로 줄어드는 역할을 한다.

위의 표(배열)로 예시를 들자면 중간 값은 5가 된다.

숫자 5와 정렬해야할 숫자인 3을 비교하면 작기 때문에 왼쪽으로 범위를 줄일 수 있다.

 

1

2

3

4

5

 

 

 

그리고 나서 줄여진 절반의 배열에서 중간 값을 구하면 3인데, 이 때 3은 작거나 같은 쪽에 속하기 때문에 왼쪽으로 범위를 줄인다.

 

1

2

3

 

 

 

이걸 이런 식으로 계속 반복하다보면 결국에는 3만 남을텐데, 그럼 그 위치에 추가를 하는 식으로 진행한다.

 

 

 

 

근데 이번 문제에서 이게 적용을 이렇게 시킬줄은 몰랐다..