package baekjoon;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class b10816 {
public static int lowerBound(int arr[], int key) {
int start = 0; int end = arr.length;
while(start < end){
int mid = (start+end)/2;
if(key <= arr[mid]) {
end = mid;
} else {
start = mid+1;
}
}
return end;
}
public static int upperBound(int [] arr, int key) {
int start = 0; int end = arr.length;
while(start < end) {
int mid = (start+end)/2;
if(key < arr[mid]) {
end = mid;
} else {
start = mid+1;
}
}
return end;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
int arr[] = new int[N];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
int M = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for(int i = 0; i < M; i++) {
int key = Integer.parseInt(st.nextToken());
sb.append(upperBound(arr,key) - lowerBound(arr,key)).append(' ');
}
System.out.println(sb);
}
}
lowerBound : 데이터 내 특정 키값보다 같거나 큰 값이(키 값 이상의 값이) 처음 나오는 위치를 리턴
upperBound : 특정 키 값보다 처음으로 큰 값(키 값 초과하는 값)이 나오는 위치를 리턴
*중복된 값이 있는 배열을 정렬한 상태여야함.
여기서 주의해야할 점
이진 탐색과 다른 점이 있다. 주어진 값보다 같거나 큰 값이 처음으로 나오는 것을 리턴해야함. 만약 위 경우에서 키 값이 7이라면 주어진 배열의 크기만큼 리턴되어야 하기 때문에 high(end) 값을 arr.length-1 이 아닌 arr.length로 설정 해주어야 한다.
그리고 lowerBound와 upperBound에서 high와 low가 같아지는 값을 리턴하기 때문에 return start = end 똑같다.
'Problems & Solutions' 카테고리의 다른 글
16139 인간-컴퓨터 상호작용 (0) | 2022.08.10 |
---|---|
2559 수열 (0) | 2022.08.08 |
1920 수 찾기 (0) | 2022.08.05 |
19941 햄버거 분배 (0) | 2022.08.05 |
7795 먹을 것인가 먹힐 것인가 (0) | 2022.07.30 |