[백준_10816] 숫자 카드 2 - JAVA
15341 단어 이분탐색정렬실버4백준 Class 2백준 Class 2
문제 출처
풀이
- 이분 탐색으로 풀 수 있는 문제이지만, 처음 보는 유형이였다.
- upper bound와 lower bound를 이용해 찾으려는 Key 값의 최소 시작 index와 최대 끝 index를 찾아서 풀 수 있는 문제이다.
- https://st-lab.tistory.com/267 의 풀이를 참고하여 풀었다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
int N = Integer.parseInt(stringTokenizer.nextToken());
int[] arr = new int[N];
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
for (int i = 0; i < N; i++) {
arr[i] = Integer.valueOf(stringTokenizer.nextToken());
}
Arrays.sort(arr);
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
int M = Integer.parseInt(stringTokenizer.nextToken());
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < M; i++) {
int key = Integer.parseInt(stringTokenizer.nextToken());
stringBuilder.append(upperBound(arr, key) - lowerBound(arr, key)).append(" ");
}
System.out.println(stringBuilder);
}
public static int lowerBound(int[] arr, int key) {
int lo = 0;
int hi = arr.length;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (key <= arr[mid]) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
public static int upperBound(int[] arr, int key) {
int lo = 0;
int hi = arr.length;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (key < arr[mid]) {
hi = mid;
} else {
lo = mid + 1;
}
}
return lo;
}
}
채점 결과
Author And Source
이 문제에 관하여([백준_10816] 숫자 카드 2 - JAVA), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jm_25/백준10816-숫자-카드-2-JAVA저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)