9-8: 숫자 개수 세기

숫자 개수 세기 (count.cpp)

 

문제

---

n개의 숫자가 주어지고, q개의 질문이 주어진다. 각각의 질문은 n개의 숫자 중에서 특정 숫자가 몇개나 있는지를 묻는다. q개의 질문에 모두 답하는 프로그램을 작성하시오.

 

입력

---

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

출력

---

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

예제 입력

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

예제 출력

2
3
0
1

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

public class count {

    /**
     *
     * 문제:
     * n개의 숫자가 주어지고, q개의 질문이 주어진다.
     * 각각의 질문은 n개의 숫자 중에서 특정 숫자가 몇개나 있는지를 묻는다.
     * q개의 질문에 모두 답하는 프로그램을 작성하시오.
     *
     *
     * 입력:
     * 첫 번째 줄에 숫자의 개수 n, 그리고 질문의 개수 q가 주어진다 ( 1 ≤ n ≤ 100,000, 1 ≤ q ≤ 100,000)
     * 두 번째 줄에 n개의 숫자가 주어진다. 세 번째 줄에 q개의 질문이 주어진다.
     *
     *
     * 출력:
     * 각 질문에 대하여 숫자의 개수를 한 줄에 하나씩 출력한다.
     *
     *
     * 예제 입력:
     * 10 4
     * 1 3 4 3 2 3 1 2 5 10
     * 1 3 9 10
     *
     *
     * 예제 출력:
     * 2
     * 3
     * 0
     * 1
     *
     *
     * @param args
     */

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int Q = Integer.parseInt(st.nextToken());

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

        Arrays.sort(nums);

        //bin search for each elem and look left+right to get their count.
        st = new StringTokenizer(br.readLine());
        for (int i=0; i<Q; i++){
            int target = Integer.parseInt(st.nextToken());
            System.out.println(binarySearch(nums, 0, nums.length-1, target)+" ");
        }


    }

    private static int binarySearch(int[] nums, int start, int end, int target) {
        while (start <= end){
//            System.out.println("start : " + start+ ", end: " + end);
            int mid = (start+end) / 2;

            if (nums[mid] > target){
                //search lower half
                end = mid-1;
            } else if (nums[mid] < target){
                //search upper half
                start = mid+1;
            } else return countElementsWithValue(nums, mid);
        }
        return 0;
    }

    private static int countElementsWithValue(int[] nums, int mid) {
        //we know mid index contains target number.
        int count = 1;
        //look left
        int start = mid-1;
        while (start >=0 && nums[start] == nums[mid]){
            count++;
            start--;
        }

        start = mid+1;
        while (start <= nums.length -1 && nums[start] == nums[mid]){
            count++;
            start++;
        }
        return count;
    }
}