[필수 문제] 숫자 개수 세기

1. 문제

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

 

 

 

2. 풀이

숫자 개수 세기는 이진 탐색을 이용해야한다. 이진 탐색은 정렬된 배열에서 찾고자 하는 값을 보다 빠르게 탐색하는 방법이다. 따라서 주어진 값들을 정렬하고, 정렬된 값에서 찾고자 하는 값의 시작과 끝의 위치를 파악한뒤, 갯수를 출력하면 된다.

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

public class Main {

    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    private static int n;
    private static int q;
    private static int[] arr;

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        q = Integer.parseInt(st.nextToken());

        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);

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < q; i++) {
            int num = Integer.parseInt(st.nextToken());

            int start = findStart(num);
            int end = findEnd(num);

            if(start == -1) bw.write("0\n");
            else bw.write((end-start + 1) + "\n");
        }

        br.close();
        bw.flush();
        bw.close();
    }

    private static int findStart(int value) {
        int s = 0;
        int e = 0;

        // 시작 위치의 값은 찾고자 하는 값보다 작아야함
        if(arr[0] < value) s = 0;
        else {
            if(arr[0] > value) return -1;
            else return 0;
        }

        // 끝 위치의 값은 찾고자 하는 값보다 커야함
        if(arr[n-1] >= value) e = n-1;
        else return -1;

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

            if(arr[mid] < value) s = mid;
            else e = mid;
        }

        if(arr[e] == value) return e; // e의 위치가 찾고자 하는 값과 동일할 경우
        else return -1; // 찾고자 하는 값이 없을 경우
    }

    private static int findEnd(int value) {
        int s = 0;
        int e = 0;

        // 시작 위치의 값은 찾고자 하는 값보다 작아야함
        if(arr[0] <= value) s = 0;
        else return -1;

        // 끝 위치의 값은 찾고자 하는 값보다 커야함
        if(arr[n-1] > value) e = n-1;
        else {
            if(arr[n-1] < value) return -1;
            else return n-1;
        }

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

            if(arr[mid] > value) e = mid;
            else s = mid;
        }

        if(arr[s] == value) return s; // s의 위치가 찾고자 하는 값과 동일할 경우
        else return -1; // 찾고자 하는 값이 없을 경우
    }

}