https://www.acmicpc.net/problem/10816
코드설명
이 문제는 HashMap, 배열, 이분탐색 을 활용하여 풀 수 있는 문제입니다.
HashMap과 배열을 사용하면 쉽게 풀수 있지만, 이분탐색으로 풀어보고싶어서 이분탐색으로 접근했습니다.
이 문제의 핵심은
lowerBound를 통해 해당 target을 포함하는 숫자의 Index를 가져옵니다.
upperBound를 통해 해당 target을 포함하는 숫자의 Index + 1 을 가져옵니다.
이 과정에서 일반적인 이분탐색과 다릅니다.
일반적인 이분탐색을 사용할경우
for(int i=0;i<M;i++) {
int answer = 0;
int startIdx = 0, endIdx = N - 1;
int target = Integer.parseInt(st.nextToken());
while(startIdx <= endIdx) {
int mid = ( startIdx + endIdx) / 2;
if(A[mid] == target) {
answer = 1;
break;
}
if(A[mid] < target) startIdx = mid + 1;
else if (A[mid] > target) endIdx = mid - 1;
}
System.out.println(answer);
}
- 위의 코드와 같이 endIdx = N -1, 종료조건은 startIdx <= endIdx 입니다.
하지만, upperBound와 lowerBound를 구현할시에는 startIdx와 endIdx가 같아진다면 바로 종료시키는 처리를 통해 진행했습니다.
또한 LowerBound 같은경우 target 과 A[midIdx]가 <= 처리를 통해 10, 10, 10 이 있을때 endIdx가 startIdx로 이동하게 처리합니다.
upperBOund같은경우 target과 A[midIdx] 를 < 처리를 통해\ 둘의 값이 같아질때, 즉 10 , 10 , 10 이 있을때 startIdx가 endIdx쪽으로 다가오도록 처리했습니다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static int N;
public static int[] A;
public static int M;
public static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
A = new int[N];
st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++) {
A[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(A);
st = new StringTokenizer(br.readLine());
M = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
for(int j=0;j<M;j++) {
int target = Integer.parseInt(st.nextToken());
int lowerBoundValue = lowerBound(target);
int upperBoundValue = upperBound(target);
// System.out.print(upperBoundValue - lowerBoundValue+" ");
sb.append(upperBoundValue - lowerBoundValue).append(" ");
}
System.out.println(sb.toString());
}
//target의 가장 작은 작은 Index
public static int lowerBound(int target) {
int startIdx = 0;
int endIdx = N;
while(startIdx < endIdx) {
int midIdx = (startIdx + endIdx) / 2;
if(target <= A[midIdx]) {
endIdx = midIdx;
}else {
startIdx = midIdx + 1;
}
}
return endIdx;
}
//target의 가장 큰 Index 보다 한 칸 더 높음
public static int upperBound(int target) {
int startIdx = 0;
int endIdx = N;
while(startIdx < endIdx) {
int midIdx = (startIdx + endIdx ) / 2;
if(target < A[midIdx]) {
endIdx = midIdx;
}else {
startIdx = midIdx + 1;
}
}
return endIdx;
}
}
참고
'알고리즘 > binary_search' 카테고리의 다른 글
[백준] 19637 IF문 좀 대신 써줘 - 이분탐색(binary search) + 시간초과 JAVA (0) | 2023.07.27 |
---|---|
[백준] 2512 예산 - 파라메트릭 서치(Paramatric Search) JAVA (0) | 2023.07.27 |
[백준] 2417 정수 제곱근 - 이분탐색(binary search) JAVA (0) | 2023.07.26 |
[백준] 10815 숫자 카드 - 이분탐색(binary search) JAVA (0) | 2023.07.26 |
[백준] 1920 수 찾기 - 이분탐색(binary search) JAVA (0) | 2023.07.19 |