[백준] 10816번 : 숫자 카드 2 JAVA (이분탐색)

JAVA / 숫자 카드 2

 

 

---

 

 

문제

 

 

 

문제 해결

 

이분탐색을 통해 결과를 출력해야한다. 배열 중에 특정 key에 대해 찾는 것은 경험해봤지만, 중복되는 key 갯수를 count 하는 건 낯설다. 찾아보니 C에는 lower_bound와 upper_bound 라는 메서드가 구현되어있지만 자바에는 없다. binarySearch()로 lower_bound의 형식만 제공한다.

lower_bound(하한)이란 찾고자 하는 값 이상의 값이 처음으로 나타나는 위치를 의미

 

upper bound (상한)이란 찾고자 하는 값을 초과한 값을 처음 만나는 위치를 의미

중복 원소에 대한 길이 =  (상한 - 하한) 

 

나의 풀이

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


public class Main {

    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StringBuilder sb = new StringBuilder();
    public static int N,M, num;
    public static Integer[] arr1;

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        arr1 = new Integer[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            arr1[i] = Integer.parseInt(st.nextToken());
        } // arr1 완성
        Arrays.sort(arr1);

        M = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < M; i++) {
            num = Integer.parseInt(st.nextToken());
            sb.append(upperBound(num) - lowerBound(num)).append(" ");
        }

        bw.write(sb.toString().trim());
        bw.flush();
        bw.close();
    }

    public static int lowerBound(int key){
        int left = 0;
        int right = arr1.length;

        while(left < right){
            int mid = (left + right) / 2;
			// 10을 찾는다하면 10의 시작 index 찾아간다.
            if(key <= arr1[mid]){
                right = mid;
            }else{
                left = mid + 1;
            }
        }

        return left;
    }

    public static int upperBound(int key){
        int left = 0;
        int right = arr1.length;

        while(left < right){
            int mid = (left + right) / 2;
			
        // 10을 찾는다하면 10의 마지막 인덱스의 다음 index 찾을때까지.
            if(key < arr1[mid]){
                right = mid;
            }else{
                left = mid + 1;
            }
        }

        return left;
    }
}

 

참고

https://st-lab.tistory.com/267

[백준] 10816번 : 숫자 카드 2 - JAVA [자바]