백준 10816 자바(이진탐색)

종전의 이진탐색 문제보다 신경쓸게 많다.전 문제는 단순히 존재 유무만 따지면 됐기에 간단했지만 이번엔 중복 개수를 얻어내야 한다.

lower upper 개념을 알고 있어야 한다.

import java.util.*;
import java.io.*;

class Main{
    public static void main(String[] args) throws IOException{
      Scanner sc = new Scanner(System.in);

      int N = sc.nextInt();
      int[] arr = new int[N];
      
      for(int i=0;i<N;i++){
        arr[i] = sc.nextInt();
      }
      Arrays.sort(arr);

      int M = sc.nextInt();

      StringBuilder sb = new StringBuilder();

      for(int i=0;i<M;i++){
        int key = sc.nextInt();
        int upper = Upper(key,arr);
        int lower = Lower(key,arr);
        sb.append(upper-lower).append(" ");
      }
      System.out.println(sb);
    }

    public static int Upper(int key,int[] arr){
        int lo = 0;
        int hi = arr.length; // 이 부분에서 애를 먹었다.

        while(lo <up){
            int mid = (lo+up)/2;
            if(key >= arr[mid]) lo = mid+1;
            else hi = mid;
        }
        return lo;
    }

    public static int Lower(int key,int[] arr){
        int lo=0;
        int hi = arr.length;

        while(lo <up){
            int mid = (lo+up)/2;
            if(key<=arr[mid]) hi = mid;
            else lo=mid+1;
        }
        return lo;
    }
}

int up = arr.length; // 이 부분에서 애를 먹었다.
처음에 up을 arr.length-1로 적었다.배열 인덱스랑 맞춰놔야 되지 않을까 싶었는데 아니었다.M 배열의 마지막 요소가 upper와 lower가 일치하면서 무조건 0이 나오는 현상이 발생했다.뒤에 배열 인덱스가 없어서 upper가 한칸 더 옆으로 못 가서 발생하는듯 했다.

arr.length로 수정하면 자연스럽게 hi가 옆으로 이동하면서 이게 고쳐지는듯 했다.