[백준] 10816. 숫자 카드 2

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

10816번: 숫자 카드 2

이분 탐색으로 그냥 해당 값이 있는지 찾기만 하면 되는 게 아니라 몇 개 있는지를 찾아야 한다. 따라서 상한선과 하한선을 찾아서 몇 개인지 개수를 계산하면 된다. 

1. 입력 값을 배열에 저장하고 배열을 정렬한다.
2. 상한선과 하한선을 찾고, (상한선 - 하한선)이 해당 값의 개수가 된다. 
   예를 들어 [1, 1, 2, 2, 2, 3]과 같이 배열이 있을 때, 값 2의 상한선은 인덱스 5, 하한선은 인덱스 2이다. 상한선은 해당 값을 포함하지 않는 초과하는 값임을 주의해야 한다.

import java.io.BufferedReader;
import java.io.IOException;

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

public class Main {

    static int n;
    static int m;
    static int[] arr;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);

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

        System.out.println(sb);
    }

    private static int upperBound(int num) {
        int min = 0;
        int max = n;
        while (min < max) {
            int mid = (min + max) / 2;
            if (arr[mid] > num) {
                max = mid;
            } else {
                min = mid + 1;
            }
        }
        return max;
    }

    private static int lowerBound(int num) {
        int min = 0;
        int max = n;
        while (min < max) {
            int mid = (min + max) / 2;
            if (arr[mid] >= num) {
                max = mid;
            } else {
                min = mid + 1;
            }
        }
        return min;
    }
}

그리고 이분 탐색말고 map을 이용해서 풀면 더 간단하게 풀 수 있다.

import java.io.BufferedReader;
import java.io.IOException;

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

public class Main {

    static int n;
    static int m;
    static Map<Integer, Integer> map = new HashMap();
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            int key = Integer.parseInt(st.nextToken());
            map.put(key, map.getOrDefault(key, 0) + 1);
        }

        m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            int key = Integer.parseInt(st.nextToken());
            sb.append(map.getOrDefault(key, 0) + " ");
        }

        System.out.println(sb);
    }
}

이분 탐색은 아직 어렵다.. 이 문제가 이분 탐색을 연습하기 좋은 문제인 거 같다!