숫자 카드 2 - 10816 - 중요!!

문제

풀이

import java.util.*;

// 숫자 카드2 - 정렬 - S4
public class ex10816 {

    static int n,m;
    static int[] arr;
    static int[] brr;

    // 최저 지점
    public static int lowerSearch(int[] arr,int key){
        int lt=0;
        int rt=arr.length;

        while(lt<rt){
            int mid = (lt+rt)/2;

            if(key<=arr[mid]) rt=mid;
            else lt=mid+1;
        }
        return lt;
    }

    // 초과 지점
    public static int upperSearch(int[] arr,int key){
        int lt=0;
        int rt=arr.length;

        while(lt<rt){
            int mid = (lt+rt)/2;

            if(key<arr[mid]) rt=mid;
            else lt=mid+1;
        }
        return lt;
    }
    
    public static void solution(){
        Arrays.sort(arr);
        StringBuilder sb = new StringBuilder();
        for(int x : brr){
            sb.append(upperSearch(arr,x) - lowerSearch(arr,x)).append(' ');
        }
        System.out.println(sb);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

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

        m = sc.nextInt();
        brr = new int[m];
        for(int i=0; i<m; i++){
            brr[i] = sc.nextInt();
        }

        solution();
    }
}

처음 문제를 봤을때 Hashmap으로 푸는 법과 이분탐색 두가지로 푸는 법이 생각났다. 근데 이분탐색으로 해결하는 게 더 공부가 될 것 같아 그렇게 풀었다.

우선 탐색해서 존재유무를 파악하는 것보다 한발 더 나아가서 갯수를 구하는 법이다.
이런 경우는 해당 문자를 정렬된 상태에서 젤 최저 인덱스와 초과 인덱스의 차를 구해서 몇개인지 출력해야한다.

lowerSearch() , upperSearch()를 각각 메소드를 만들어서 이분탐색과정을 통해
최저 인덱스 , 초과 인덱스를 뽑아낸다.

lowerSearch() 에서는 최저지점을 찾아야하기 떄문에 rt를 계속 줄여주고,
upperSearch() 에서는 초과지점을 찾아야하기 때문에 lt를 계속 늘려주고, rt를 넘어서는 순간까지 while문을 돌리고 return!