문제

BOJ 10816: 숫자 카드 2 https://www.acmicpc.net/problem/10816

풀이

조건

• 숫자 카드 N개를 가지고 있다.
• 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 몇 개 가지고 있는지 구한다.
• 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다.
• 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

풀이 순서

• 이분 탐색을 사용한다.
  • 숫자 카드를 정렬한 상태로 이분 탐색을 실시해야한다.
• 찾아야 하는 숫자가 있는 인덱스의 가장 작은 값과 가장 큰 값을 구해 빼면 해당 숫자의 개수를 구할 수 있다.
• 최소 인덱스 찾기
  • 이분 탐색을 하던 중 목표값을 찾았다면 더 작은 인덱스에 해당 값이 있을 수 있으므로 아래쪽 범위를 더 탐색한다.
• 최대 인덱스 찾기
  • 이분 탐색을 하던 중 목표값을 찾았다면 더 큰 인덱스에 해당 값이 있을 수 있으므로 위쪽 범위를 더 탐색한다.

코드

Java

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine()); // 가지고 있는 숫자 카드 개수

        int[] cards = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            cards[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(cards);

        int M = Integer.parseInt(br.readLine()); // 구해야 되는 수

        int[] targets = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < M; i++) {
            targets[i] = Integer.parseInt(st.nextToken());
            int result = findByBinarySearch(cards, 0, N - 1, targets[i]);
            sb.append(result).append(" ");
        }

        System.out.println(sb);
    }

    static int findByBinarySearch(int[] arr, int start, int end, int target) {

        int s = start;
        int e = end + 1; // 배열의 길이를 인덱스로 넘겨줌(N = end + 1)

        // 최소 인덱스 찾기
        while (s < e) {
            int mid = (s + e) / 2;
            
            // 목표 값이 mid에 있는 값보다 작거나 같다면 -> e 값을 mid 위치로 이동
            if (target <= arr[mid]) {
                e = mid;
            } 
            // 목표 값이 mid에 있는 값보다 크다면 -> s 값을 mid + 1 위치로 이동
            else {
                s = mid + 1;
            }
        }

        int minIdx = s; // 목표 값이 있는 최소 인덱스

        // 최대 인덱스 찾기
        s = start;
        e = end + 1;

        while (s < e) {
            int mid = (s + e) / 2;

            // 목표 값이 mid에 있는 값보다 작다면 -> e 값을 mid 위치로 이동
            if (arr[mid] > target) {
                e = mid;
            }
            // 목표 값이 mid에 있는 값보다 크거나 같다면 -> s 값을 mid + 1 위치로 이동
            else {
                s = mid + 1;
            }
        }

        int maxIdx = s; // 목표 값이 있는 최고 인덱스 + 1

        return maxIdx - minIdx;
    }
}

정리

• 이분 탐색을 구현하는 연습을 더 해야겠다.