jetalog.net

문제

n개의 숫자가 주어지고, q개의 질문이 주어진다.

각각의 질문은 n개의 숫자 중에서 특정 숫자가 몇개나 있는지를 묻는다.

q개의 질문에 모두 답하는 프로그램을 작성하시오.

입력

첫 번째 줄에 숫자의 개수 n, 그리고 질문의 개수 q가 주어진다. ( 1 ≤ n ≤ 100,000, 1 ≤ q ≤ 100,000)
두 번째 줄에 n개의 숫자가 주어진다.
세 번째 줄에 q개의 질문이 주어진다.
주어지는 q개의 질문에 해당하는 숫자 범위는 100,000,000이하이다.

출력

각 질문에 대하여 숫자의 개수를 한 줄에 하나씩 출력한다.

입력 예시

10 4
1 3 4 3 2 3 1 2 5 10
1 3 9 10

출력 예시

2
3
0
1

코드

Java

import java.util.*;
 
public class Main{
    public static int[] numbers;
 
    public static int binarySearch(int start, int end, int target) {
        if (start > end) return -1;
        if (start == end) return (numbers[start] == target) ? start : -1;
 
        int mid = (end + start) / 2;
 
        if (numbers[mid] == target) return mid;
        if (numbers[mid] < target) return binarySearch(mid + 1, end, target);
        if (numbers[mid] >= target) return binarySearch(start, mid, target);
 
        return -1;
    }
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String[] buf;
 
        buf = scan.nextLine().split(" ");
        int numberCnt = Integer.parseInt(buf[0]);
        int questionCnt = Integer.parseInt(buf[1]);
        numbers = new int[numberCnt];
 
        buf = scan.nextLine().split(" ");
        for (int i = 0; i < numberCnt; i++) {
            numbers[i] = Integer.parseInt(buf[i]);
        }
 
        Arrays.sort(numbers);
 
        buf = scan.nextLine().split(" ");
        int answer, target;
        for (int i = 0; i < questionCnt; i++) {
            answer = 0;
            target = Integer.parseInt(buf[i]);
 
            int index = binarySearch(0, numberCnt - 1, target);
            if (index < 0) {
                System.out.println(0);
                continue;
            }
            answer++;
            for (int j = index - 1; j >= 0 && numbers[j] == target; j--) answer++;
            for (int j = index + 1; j < numbers.length && numbers[j] == target; j++) answer++;
            System.out.println(answer);
        }
    }
}