[이진 탐색] 백준 10816번 숫자 카드2(Java)

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

10816번: 숫자 카드 2

📚 문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

 

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1<=N<=500,000)이 주어진다.

둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 

셋째 줄에는 M(1<=M<=500,000)이 주어진다.

넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어진다.

 

예제 입력	예제 출력
10 6 3 2 10 10 10 -10 -10 7 3 8 10 9 -5 2 3 4 5 -10	3 0 0 1 2 0 0 2

 

📝 문제 해결

이코테 정렬된 배열에서 특정 수의 개수 구하기와 비슷한 문제로

상근이가 가지고 있는 숫자 카드에서 구해야하는 카드의 숫자가 처음 등장하는 인덱스와 x가 마지막으로 등장하는 인덱스를 각각 계산한 뒤에, 그 인덱스의 차이를 계산하면 문제를 해결할 수 있다.

= 찾고자 하는 숫자값을 초과하는 값이 처음 나타는 인덱스 -  찾고자 하는 숫자값 이상의 값이 처음으로 나타나는 인덱스

 

💻 코드

package search;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ10816 {

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

        int N = Integer.parseInt(br.readLine());
        int[] 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);

        int M = Integer.parseInt(br.readLine());

        st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        for(int i=0; i<M; i++){
            int target = Integer.parseInt(st.nextToken());

            int left = leftIndex(arr, 0, N, target);
            int right = rightIndex(arr, 0, N, target);
            sb.append(right-left).append(' ');

        }

        System.out.print(sb);
    }

    public static int leftIndex(int[] arr, int start, int end, int target){
        while(start < end){
            int mid = (start+end)/2;
            if(arr[mid] >= target) end = mid;
            else start = mid+1;
        }
        return end;
    }

    public static int rightIndex(int[] arr, int start, int end, int target){
        while(start < end){
            int mid = (start+end)/2;
            if(arr[mid] > target) end = mid;
            else start = mid+1;
        }
        return end;
    }
}

 

🔽 비슷한 문제

[이진 탐색] 이코테 정렬된 배열에서 특정 수의 개수 구하기(Java)