1. 백준 3020 개똥벌레

1.이분탐색을 위해서 왜 배열들을 정렬하는지 모르겠다.
2. H를 기준으로 for문 도는 이유.

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

public class Main {

    static int N,H;
    static int[] upObstacle;
    static int[] downObstacle;


    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());

        upObstacle = new int[N/2];
        downObstacle = new int[N/2];

        for (int i = 0; i < N / 2; i++) {
            downObstacle[i] = Integer.parseInt(br.readLine());
            upObstacle[i] = Integer.parseInt(br.readLine());
        }
		// 해당부분
        Arrays.sort(upObstacle);
        Arrays.sort(downObstacle);

        int minObstacle = Integer.MAX_VALUE;
        int count = 0;

        for (int i = 1; i <= H; i++) {
            int downCount = binarySearch(downObstacle, i);
            int upCount = binarySearch(upObstacle, H - i + 1);

            int current = downCount + upCount;

            if (current < minObstacle) {
                minObstacle = current;
                count = 1;
            } else if (current == minObstacle) {
                count++;
            }
        }

        System.out.println(minObstacle + " " + count);


    }

    private static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        int resultIndex = arr.length;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] >= target) {
                resultIndex = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return arr.length - resultIndex;
    }
}

solve

{1, 2, 3, 4, 5} 배열 있을 때, 크기 3 이상의 인덱스는 2.
마지막에 arr.length - resultIndex 의미는 부딪히는 개수.
5 - 2 = 3. 부딪히는 수를 count로 하여 반환.

1. taget 보다 크거나 같은, 최소 인덱스를 구하기 위함.

2. 반복문을 1 ~ H까지 돌면서, 해당 높이에서의 count값을 구함. 계속 돌면서 더 작은 값이 있을 시 result에 넣어줌.

내가 헷갈린 부분

내가 떠올렸던 생각 : H 자체를 이분탐색 돌아야겠다. 그런데 문제가 있음. 이분탐색은 정렬되어있어야 한다. 내가 H로 이분탐색 돌리기엔, H의 값이 작아지든 커지든 그에 비례해서 count가 변화하지 않음.

배운 부분

• 이분탐색 활용해 특정 값 뽑는 것 뿐만 아닌, index를 얻어낼 수도 있다.