백준 10816 - 숫자 카드 2

문제

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

10816번: 숫자 카드 2

 

 

풀이

숫자를 찾을 때 이분 탐색을 이용해 빠르게 찾을 수 있다. 같은 숫자를 여러 개 찾아야하는데 이분 탐색을 이용해 상한선과 하한선을 찾는다. 

 

 

코드

java

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    static int N, M;
    static int[] a, b;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        input();
        solve();
    }

    private static void solve() {
        Arrays.sort(a);
        for (int i = 0; i < M; i++) {
            int cnt = upperBound(a, 0, N - 1, b[i]) - lowerBound(a, 0, N - 1, b[i]);
            if (cnt == -1) cnt = 0;
            sb.append(cnt).append(" ");
        }
        System.out.println(sb.toString());
    }

    private static int lowerBound(int[] arr, int l, int r, int x) {
        int idx = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (arr[mid] > x) {
                r = mid - 1;
            } else if (arr[mid] < x) {
                l = mid + 1;
            } else {
                idx = mid;
                r = mid - 1;
            }
        }
        return idx;
    }

    private static int upperBound(int[] arr, int l, int r, int x) {
        int idx = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (arr[mid] > x) {
                r = mid - 1;
            } else if (arr[mid] < x) {
                l = mid + 1;
            } else {
                idx = mid;
                l = mid + 1;
            }
        }
        if (idx != -1) idx++;
        return idx;
    }

    private static void input() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        a = new int[N];
        for (int i = 0; i < N; i++)
            a[i] = sc.nextInt();
        M = sc.nextInt();
        b = new int[M];
        for (int i = 0; i < M; i++)
            b[i] = sc.nextInt();
        sc.close();
    }
}