숫자개수 세기

숫자 개수 세기 (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.util.*;

public class Main {

    public static ArrayList<Integer> box = new ArrayList<>();
    public static long result;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //총 몇개의 숫자를 입력 받을 것인지
        int a;
        int b;
        long c[];
        int d[];
        int count = 0;
        long max = Integer.MIN_VALUE;
        a = sc.nextInt();
        b = sc.nextInt();
        c = new long[a];

        for (int i = 0; i < a; i++) {
            c[i] = sc.nextLong();
            if (c[i] > max) max = c[i];
        }

        sort(c, 0, a - 1);


        for (int i = 0; i < b; i++) {
            long find = sc.nextLong();
            System.out.println(countN(0, a - 1, c, find));
        }


        sc.close();

    }

    public static int countN(int s, int e, long[] c, long b) {
        if (s > e) return 0;
        else if (s == e) {
            if (c[s] == b) return findSame(c, b, s);
            else return 0;
        } else {
            int mid = (s + e) / 2;
            Long result = c[mid];

            if (result == b) return findSame(c, b, mid);
            else if (result > b) return countN(s, mid - 1, c, b);
            else return countN(mid + 1, e, c, b);
        }

    }

    public static int findSame(long[] c, long b, int k) {

        int left = k - 1;
        int right = k;

        int count = 0;

        while (k < c.length && c[k] == b) {
            k++;
            count++;
        }

        while (left >= 0 && c[left] == b) {
            left--;
            count++;
        }

        return count;
    }


    public static void sort(long[] data, int l, int r) {
        int left = l;
        int right = r;
        long pivot = data[(l + r) / 2];

        do {
            while (data[left] < pivot) left++;
            while (data[right] > pivot) right--;
            if (left <= right) {
                long temp = data[left];
                data[left] = data[right];
                data[right] = temp;
                left++;
                right--;
            }
        } while (left <= right);

        if (l < right) sort(data, l, right);
        if (r > left) sort(data, left, r);
    }


}