문제
n개의 숫자가 주어지고, q개의 질문이 주어진다. 각각의 질문은 n개의 숫자 중에서 특정 숫자가 몇개나 있는지를 묻는다. q개의 질문에 모두 답하는 프로그램을 작성하시오.
입력
첫 번째 줄에 숫자의 개수 n, 그리고 질문의 개수 q가 주어진다 ( 1 ≤ n ≤ 100,000, 1 ≤ q ≤ 100,000) 두 번째 줄에 n개의 숫자가 주어진다. 세 번째 줄에 q개의 질문이 주어진다. 주어지는 q개의 질문은 모두 1000이하이다.
출력
각 질문에 대하여 숫자의 개수를 한 줄에 하나씩 출력한다.
예제 입력
10 4
1 3 4 3 2 3 1 2 5 10
1 3 9 10
예제 출력
2
3
0
1이 문제가 너무너무너무 안풀려서 며칠동안 고민한 결과 겨우겨우 세번째 시도만에 풀게 되었다.
입력이 10만개 이기 때문에 빠른 정렬과 이진탐색으로 푸는 문제이다. 나는 합병정렬까지는 뭐 쉽게 했는데 그 뒤가 문제였다.
이진탐색은 중복된 숫자가 없는 배열에서 1개의 숫자를 찾는 코드를 알고 있었는데, 여기에서는 여러개의 숫자를 찾아야되서 고민을 했다.
내가 한 첫번째 시도는 이진탐색으로 숫자를 찾고 숫자의 앞뒤로 다른숫자가 나올때 까지 while로 찾았는데, 당연히 이렇게 풀면
시간초과가 떠서 실패를 했다.
두번째 시도는 선생님한테 힌트를 얻어 예를 들어 1 2 3 3 3 4 4 5 5 라는 배열이 있을때 3의 개수를 찾아보면 3의 앞자리 2를 찾고,
3의 바로 뒤에 있는 수인 4를 찾아서 둘의 인덱스를 빼고 다시 거기에서 1을 빼면 3의 개수가 나오기 때문에 그렇게 시도를 해보았지만,
이렇게 문제를 풀게 되면 문제점이 몇가지 있었다. 배열에 없는 숫자를 찾을 때 문제가 생기고, 배열의 처음과 끝에 있는 숫자를 찾을 때
문제가 생겨서 코드를 짜면 짤수록 미궁에 빠졌다. 그래서 이 방법 또한 구현을 하다가 포기했다.
마지막으로 한 시도는 1 2 3 3 3 4 4 5 5 에서 3의 개수를 찾을때 처음 3의 인덱스 번호 '2'를 찾고 마지막 3의 인덱스 '4'를 찾아서 두개를
빼고나서 1을 더하면 개수가 나오는 방식이였다. 이렇게 하게 된다면 배열의 처음과 끝의 수에서도 문제가 되지 않고, 재귀호출로 이진탐색을
구현할 때 찾으려는 숫자가 없을 때에도 그냥 -1을 리턴해주면 되기 때문에 구현 할 수 있다고 생각했다.
그래서 먼저 찾는 숫자의 제일 왼쪽 인덱스를 반환하는 left_idx 와 right_idx 함수를 이진탐색으로 구현해서 풀었다.