숫자카드2

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

 

* 기본적인 upperBound, lowerBound를 구하는 문제.

* binarySearch로 기본적인 코드를 알면 등호만 붙여주면 끝나는 문제다.

 

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

class BOJ10816 {
    static int size, targetSize;
    static int[] arr, target;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        size = Integer.parseInt(br.readLine());
        arr = new int[size];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < size; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);
        targetSize = Integer.parseInt(br.readLine());
        target = new int[targetSize];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < targetSize; i++) {
            target[i] = Integer.parseInt(st.nextToken());
        }
        for(int t : target) {
            int low = lowerBound(t);
            int up = upperBound(t);
            sb.append(up-low).append(" ");
        }
        System.out.println(sb);
    }
    private static int lowerBound(int target) {
        int left = 0, right = arr.length;
        while(left < right) {
            int mid = (left+right)/2;
            if(arr[mid] >= target) {
                right = mid ;
            }
            else {
                left = mid + 1;
            }
        }
        return left;
    }
    private static int upperBound(int target) {
        int left = 0, right = arr.length;
        while(left < right) {
            int mid = (left+right)/2;
            if(arr[mid] > target) {
                right = mid;
            }
            else {
                left = mid + 1;
            }
        }
        return left;
    }
}

 

- 기본적으로 최댓값을 return 해야 하기 때문에 left를 반환해야한다.

- 찾는 값 ( target ) 현재 값 ( arr[mid] ) 보다 같거나 작으면 lower.

- 찾는 값 ( target ) 현재 값 ( arr[mid] ) 보다 작으면 upper 범위이다.

- right 길이는 arr.length 길이 그 자체를 작성해주면 된다.