[백준] 10816) 숫자 카드 2 - Silver 4

[jusung-c]

문제 링크

https://acmicpc.net/problem/10816

문제 조건

숫자 카드 N개가 있을 때 M개의 수열 원소 숫자를 몇 개 가지고 있는지 구하라

• 1 ≤ N ≤ 500,000
• 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.
• 1 ≤ M ≤ 500,000
• M도 마찬가지로 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

---

아이디어

주어진 배열의 범위가 심상치 않다. 이분탐색으로 탐색 시간을 줄여보자

1. 검색 범위인 N개의 숫자 카드를 정렬한다.
2. 타겟 배열을 순회하면서 이분 탐색으로 다음 조건의 인덱스를 구한다.
   • 타겟보다 큰 수 중 가장 작은 값의 인덱스 bigIndex
   • 타겟보다 작은 수 중 가장 큰 값의 인덱스 smallIndex
3. bigIndex - smallIndex - 1로 타겟과 동일한 수의 개수를 구한다.

---

구현

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br;
    static StringTokenizer st;
    static int N, M;
    static int[] arr;

    public static void init() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        arr = new int[N];

        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 target = Integer.parseInt(st.nextToken());

            // 큰 수 중 가장 작은 값의 인덱스 구하기
            int bigIndex = bigSearch(target);

            // 작은 수 중 가장 큰 값의 인덱스 구하기
            int smallIndex = smallSearch(target);

            bw.write(bigIndex - smallIndex - 1 + " ");
        }

    }

    private static int smallSearch(int target) {
        int start = 0;
        int end = arr.length - 1;
        int result = start - 1;

        while (start <= end) {
            int mid = (start + end) / 2;

            // 작은 수 중 가장 큰 값의 인덱스 구하기
            if (arr[mid] == target) {
                end = mid - 1;
            } else if (arr[mid] > target) {
                end = mid - 1;
            } else if (arr[mid] < target) {
                result = mid;
                start = mid + 1;
            }
        }

        return result;
    }

    private static int bigSearch(int target) throws IOException {
        int start = 0;
        int end = arr.length - 1;
        int result = end + 1;

        while (start <= end) {
            int mid = (start + end) / 2;

            // 큰 수 중 가장 작은 값의 인덱스 구하기
            if (arr[mid] == target) {
                start = mid + 1;
            } else if (arr[mid] < target) {
                start = mid + 1;
            } else if (arr[mid] > target) {
                result = mid;
                end = mid - 1;
            }
        }

        return result;
    }

    public static void main(String[] args) throws Exception {
        init();

        bw.close();
    }
}