[SDS 알고리즘 특강 복습] 3020 개똥벌레 (이분탐색 / lowerBound)

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

 

이분탐색임을 알고 있었고, 종유석, 석순 각각의 높이를 강의에서 따로 저장했던 기억이 있었음.

+ 직전에 이분탐색, lowerBound, upperBound 알고리즘을 이해 및 암기하였음

 

이를 바탕으로 문제 아이디어, 구현까지 전부 해냄.

다만, 종유석의 lowerBound구할 때 target으로 어떤 값을 넣어야할 지에 대해 한 번 틀려서 노트에 필기하면서 오류 찾아냄.

배열의 인덱스에 대해 안햇갈리게 지정하는 방법을 모색해야할 듯.

 

전반적으로 잘 풀었음!! GOOD

 

나중에 lowerBound, upperBound 코드 까먹지 않게 복습해야함.

 

<이분탐색 , lowerBound, upperBound 정리>

이분탐색은 해당 값 or target값 위치 아무 곳 반환

lowerBound는 target 이상의 값의 위치 중 가장 빠른 것 반환

upperBound는 target 초과의 값의 위치 중 가장 빠른 것 반환

차이점	right 초기값	while문의 조건	while안의 첫번째 조건문	반환값
이분탐색	N(배열 원소 끝)	left <= right (whie안에서 return하므로)	-	mid
lowerBound	N+1(배열 바깥)	left < right	if(target <= arr[mid]) (lowerBound는 target 이상의 위치를 return)	left
upperBound	N+1(배열 바깥)	left < right	if(target < arr[mid])	left

 

 

<내 정답 코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int N, H;
    static int[] sucksoon;
    static int[] jongyou;
    static int min=987654, cnt=0;

    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());
        sucksoon = new int[N/2];
        jongyou = new int[N/2];
        for(int i=0; i<N; i++) {
            if(i%2 == 0) {
                sucksoon[i/2] = Integer.parseInt(br.readLine());
            }
            else {
                jongyou[i/2] = Integer.parseInt(br.readLine());
            }
        }
        Arrays.sort(sucksoon);
        Arrays.sort(jongyou);

        for(int h=1; h<=H; h++) {
            int boom;
            boom = N - (lowerBoundSucksoon(h) + lowerBoundJongyou(H-h+1));
//            System.out.println("lowerBoundSuck = " + lowerBoundSucksoon(h) + "| lowerBoundJong = " + lowerBoundJongyou(H - h) + "| boom = " + boom);
            if (boom < min) { // 만약 현재 높이의 박치기 개수가 최솟값보다 작으면
                min = boom;
                cnt = 0;
            }
            if (boom == min) {
                cnt++;
            }
        }
        System.out.println(min + " " + cnt);
    }
    static int lowerBoundSucksoon(int target) {
        int left = 0;
        int right = N/2;
        int mid;
        while(left < right) {
            mid = (left + right) / 2;
            if(target <= sucksoon[mid]) {
                right = mid;
            }
            else {
                left = mid + 1;
            }
        }
        return left;
    }
    static int lowerBoundJongyou(int target) {
        int left = 0;
        int right = N/2;
        int mid;
        while(left < right) {
            mid = (left + right) / 2;
            if(target <= jongyou[mid]) {
                right = mid;
            }
            else {
                left = mid + 1;
            }
        }
        return left;
    }
    /*
    종유석 높이, 석순 높이 각각 저장해놓고
    각 높이별로 개똥벌레가 몇개 뚫는지 계산
    근데 높이가 5 * 10^5개임, 종유석_석순 개수가 2 * 10^5개임
    단순 이중포문으로는 시간초과뜸.

    종유석, 석순 각각 오름차순 정렬해놓고
    높이별로 뚫는 개수 계산할 때 마지막인덱스 - lowerBound(현재 높이) 하면 현재높이 이상의 석순 개수가 나옴.
                 종유석 개수는  마지막인덱스 - lowerBound(H-현재높이) 하면 현재높이보다 낮은(그러니까 긴) 종유석 개수가 나옴

     이렇게 하면, Hlog(N) + Nlog(N)으로 풀림
     */

}