[BOJ-3020][이분탐색] 개똥벌레 -Java

https://www.acmicpc.net/problem/3020

3020번: 개똥벌레

package algo;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;


public class boj_3020_개똥벌레 {
	static int N,H,up[], down[];
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N=Integer.parseInt(st.nextToken());
		H=Integer.parseInt(st.nextToken());
		
		up=new int[N/2];
		down=new int[N/2];
		int upIndex=0;
		int downIndex=0;
		int min=Integer.MAX_VALUE; //충돌할 때 걸리는 수
		int cnt=1; // 그러한개 몇개가 있는가
		
		for(int i=0; i<N; i++) {
			int num=Integer.parseInt(br.readLine());
			if(i%2==0) down[downIndex++]=num;
			else up[upIndex++]=num;
		}
		
		
		Arrays.sort(up);
		Arrays.sort(down);

		for(int i=1; i<=H; i++) { //높이 1부터 H까지
			//서로 충돌개수 확인해서
			int downCrush=binarySearch(0,N/2-1 , i, down); //left, right, 현재높이, 배열
			int upCrush=binarySearch(0,N/2-1 , H-i+1, up); //left, right, 현재높이, 배열
			
			if(min>downCrush+upCrush) {
				min=downCrush+upCrush;
				cnt=1;
			}
			else if(min==downCrush+upCrush) {
				cnt++;
			}
			//현재 Min보다 작으면 Min 바꿔주고 cnt=1로 바꿔주기
			// 만약 같다면 cnt++
		}
		System.out.print(min+" "+cnt);
		
	}
	private static int binarySearch(int left, int right, int height, int[] arr) {
		int min=Integer.MAX_VALUE;
		while(left<=right) {
			int mid = (left+right)/2;
			
			if(arr[mid]>=height) { // 만약 같거나 지금높이보다 크면
				min=Math.min(min, mid);
				right=mid-1; //왼족으로 가야됨
			}
			else left=mid+1;
		}
		//다 돌고 나왓을 때
		return min==Integer.MAX_VALUE? 0 : (N/2)-min;
	}

}

소요시간 : 50분

 

 

 

이분 탐색 문제입니다..

처음에 어떤 걸 이분 탐색으로 풀어야하는지 많이 고민했습니다.

다들 아시겠지만 이분탐색으로 풀기 위해서는 배열의 정렬이 꼭 필요합니다~

 

로직을 살펴보면

 

1. 석순과 종유석을 따로따로 받아줍니다.

2. 석순과 종유석을 sort 해서 이분 탐색할 수 있게 만들어줍니다.

3. 높이를 1부터 H까지 늘려가면서 몇 개가 부딪치는지 확인합니다(이분탐색을 통해 몇개 부딪치는지 확인)

4. 최솟값과 횟수를 갱신해줍니다.

 

3번에서 이분 탐색이 필요합니다

 

현재 석순이 정렬을 했기 때문에

1 2 3 3 3 3 4처럼 정렬이 되어 있겠죠?

 

문제를 잘 보시면 석순의 높이가 1일 때 1번째 구간을 지나가면 마주치게 됩니다

즉,  석순의 높이>=현재 높이  라면 부딪칩니다.

 

이분 탐색을 통해서 내가 부딪치는 가장 왼쪽의 인덱스를 구해주면 총 몇 개가 부딪치는지 확인할 수 있습니다.

만약 동굴의 길이가 7이고 

석순을 이분 탐색했을 때의 결과가 1이라면  7-1=6 즉, 6개의 석순과 부딪친다는 걸 확인할 수 있습니다.

 

종유석도 마찬가지로 구해주면 됩니다.

 

끝~