입력
첫 번째 줄에 숫자의 개수 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
문제풀이
-
입력한 숫자를 정렬한다.(배열을 정렬한다.)
-
배열을 정렬하면 1 1 2 2 3 3 3 4 5 10 다음과 같다.(예제 입력이 주어졌을 때)
-
3의 갯수를 구한다고 했을 때 3의 시작과 끝의 index값을 구하면 총 3개의 갯수를 구할 수 있다. 갯수 = end - start +1
-
일단 for문으로 모든 경우의 수를 다 조사하게 되면 시간 복잡도가 O(n*q)가 되고 , n, q의 값이 매우 크게 되므로 총 걸리는 시간이 매우 길어진다.
-
그래서 Binary Search를 2번 해서 시작과 끝점을 찾게 되면 빠르게 갯수가 몇개인지 구할 수 있게 된다.
-
Binary Search로 구하게 되면 시간 복잡도는 O(q log n)으로 시간을 빠르게 줄일 수 있다.
