[백준 1654] 이진탐색

처음 짯던 코드는 다음과 같다

 

만들수 있는 최대 랜선의 길이를 max라 하면
모든 랜선의 길이를 더한 다음 k로 나눈 것이 

max의 최댓값이라 생각했고 거기서 n보다 크거나 같을 때까지 1씩 빼가며 max의 값을 구해주는 것이다.

 

public class Baek_1654 {
	public static void main(String[] args) throws IOException {
		//K개의 랜선을 모두 N개 이상의 같은 길이의 랜선으로 만들기
		//만들 수 있는 최대 랜선의 길이를 구해라

		//가지고 있는 랜선 갯수 1<=K<10,000, 필요한 랜선1<=N<=1,000,000
		//K<=N

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		int k = Integer.parseInt(st.nextToken());
		Long n = Long.parseLong(st.nextToken());

		Long[] arr = new Long[k];

		Long sum = 0L;
		for(int i=0; i<k; i++) {
			Long tmp = Long.parseLong(br.readLine());
			arr[i] =tmp;
			sum += tmp;
		}
		Long max = sum / k;

		//max부터 배열 돌면서 배열안 수를 max로 나눈 수 더함
		//더한 수가 n보다 같거나 크면 그 배열안 수가 결과임
		//같지 않으면 max -- 해서 계속 돌아
		int result =0;
		while (true){
			int cnt =0;
			for(Long length : arr) {
				cnt += length/max;
			}
			if(cnt >= n) break;
			max --;
		}
		System.out.println(max);
	}
}

 

짜면서 음,, 이거 아닐거같은데 ,, 했는데 역시 시간초과가 발생했고 

 

이렇게 짤 경우의 시간 복잡도는 

O(K*max)로 max부터 모든 길이마다 모든 랜선에 대해 한번씩 돌면서 길이를 찾기 때문에

K와 max가 커질 수록 효율성이 떨어진다

 

따라서 이렇게 for문으로 max값을 다 돌지 말구 이진탐색을 이용해 값을 찾도록 리팩토링을 해주었다!

 

🔎이진탐색은 

배열을 정렬 후, 중간값을 가져와 중간값과 검색값을 계속해서 비교해주는 식으로 탐색하는 것이다.

이는 검색값을 찾거나 , 더이상 중간값이 없을 때 (left > right) 까지 반복한다.

 

 

이렇게 하면 시간복잡도는 O(log max)가 돼서 훨씬 효율적으로 정답을 찾을 수 있다 ^-^

 

public class Baek_1654 {
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		int k = Integer.parseInt(st.nextToken());
		Long n = Long.parseLong(st.nextToken());

		Long[] arr = new Long[k];

		Long sum = 0L;
		for(int i=0; i<k; i++) {
			Long tmp = Long.parseLong(br.readLine());
			arr[i] =tmp;
			sum += tmp;
		}
		Long max = sum / k;

		//우리가 구해야 하는것! 최대랜선길이 : result
		long result =0;

		//가능한 최대랜선길이의 범위 : 1~max
		long left = 1;
		long right = max;
		while (left <=right) {
			long mid = (left + right) / 2;
			int cnt = 0;
			for (Long length : arr) {
				cnt += length / mid;
			}
			//cnt 값이 n보다 크거나 같다면
			//중간값이 답이거나 중간값보다 더 큰 값이 값일지두?
			//그러니까 중간값을 result에 담아주고 배열의 오른쪽 부분을 다시 탐색해준다
			if (cnt >= n) {
				result = mid;
				left = mid + 1;
			}
			//그렇지 않으면 더 작은 값중에 답이 있는 것!
			//배열의 왼쪽 부분을 탐색해준다.
			else {
				right = mid - 1;
			}
		}
		System.out.println(result);
	}
}

 

 

메모리와 시간은 다음과 같다