Java CodeTest 연습 (이분탐색)

이분탐색

• 이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다.

1. 이분 탐색을 하고자 할 때 이미 정렬이 되어있어야 합니다.

2. left, right로 미드값을 잡아줍니다.

3. mid 값과 구하고자 하는 값을 비교 합니다.

4. 비교할시 mid 값보다 구하고자 하는 값이 높으면 left를 mid+1로 만들어주고 낮으면 right를 mid-1로 만들어 줍니다.

5. left > right 가 될때까지 1~3번을 반복해서 구하고자 하는 값을 찾습니다.

이렇게 검색을 하면 전체를 검색하는 경우인 시간복잡도가 O(n) 인거에 비해서 O(log(n)) 으로 적다고 합니다.

입국심사

1차답안

import java.util.Arrays;

class Solution {
    public long solution(int n, int[] times) {
        Arrays.sort(times);
    	
    	int size = times.length;
    	int left = 1;
        int right = times[size-1] * n;
        int mid;
        int people;
        long answer = 0;
        
        while(left <= right) {
        	mid = (left + right) / 2;
        	people = 0;
        	
        	for(int time : times) {
        		people += mid/time;
        		
        		if(people >= n) {
        			answer = mid;
        			right = mid - 1;
        			break;
        		}
        	}
        	if(people < n) {
        		left = mid + 1;
        	}
        }
        return answer;
    }
}

테스트 3 시간초과 테스트 5/7/8 실패

=> Answer은 Long 타입이므로 int 타입으로 계산하게된다면 오류발생

=> Long 타입으로 타입캐스트

times[size-1] * (long) n;

2차 답안

import java.util.Arrays;

class Solution {
    public long solution(int n, int[] times) {
        Arrays.sort(times);
    	
    	int size = times.length;
    	long left = 1;
        long right = times[size-1] * (long) n;
        long mid;
        long people;
        long answer = 0;
        
        while(left <= right) {
        	mid = (left + right) / 2;
        	people = 0;
        	
        	for(int time : times) {
        		people += mid/time;
        		
        		if(people >= n) {
        			answer = mid;
        			right = mid - 1;
        			break;
        		}
        	}
        	if(people < n) {
        		left = mid + 1;
        	}
        }
        return answer;
    }
}