반응형
문제
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
코드
Java
import java.util.*;
public class Main{
public static int[] numbers;
public static int binarySearch(int start, int end, int target) {
if (start > end) return -1;
if (start == end) return (numbers[start] == target) ? start : -1;
int mid = (end + start) / 2;
if (numbers[mid] == target) return mid;
if (numbers[mid] < target) return binarySearch(mid + 1, end, target);
if (numbers[mid] >= target) return binarySearch(start, mid, target);
return -1;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String[] buf;
buf = scan.nextLine().split(" ");
int numberCnt = Integer.parseInt(buf[0]);
int questionCnt = Integer.parseInt(buf[1]);
numbers = new int[numberCnt];
buf = scan.nextLine().split(" ");
for (int i = 0; i < numberCnt; i++) {
numbers[i] = Integer.parseInt(buf[i]);
}
Arrays.sort(numbers);
buf = scan.nextLine().split(" ");
int answer, target;
for (int i = 0; i < questionCnt; i++) {
answer = 0;
target = Integer.parseInt(buf[i]);
int index = binarySearch(0, numberCnt - 1, target);
if (index < 0) {
System.out.println(0);
continue;
}
answer++;
for (int j = index - 1; j >= 0 && numbers[j] == target; j--) answer++;
for (int j = index + 1; j < numbers.length && numbers[j] == target; j++) answer++;
System.out.println(answer);
}
}
}
반응형