○ 문제 요약
상근이는 숫자 카드를 N개 가지고 있다. 다음으로 상근이가 가지고 있는 숫자 카드가 몇 개인지 구해야 할 M개의 정수가 주어진다. 주어진 정수를 상근이가 몇 개 가지고 있는지 출력하자.
○ 문제 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int[] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st ;
int N = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
arr = new int[N];
for(int i = 0 ; i < N ; i++){
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
int M = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
st = new StringTokenizer(br.readLine());
for(int i = 0 ; i < M; i++) {
int value = Integer.parseInt(st.nextToken());
sb.append(upperBound(value) - lowerBound(value)).append(" ");
}
System.out.println(sb);
}
public static int lowerBound(int value){
int lo = 0;
int hi = arr.length;
while(lo < hi){ // 둘이 같아질 때까지
int mid = (lo + hi)/2;
if(value <= arr[mid]){
hi = mid;
}else{
lo = mid +1;
}
}
return lo;
}
public static int upperBound(int value){
int lo = 0;
int hi = arr.length;
while(lo < hi){ // 둘이 같아질 때까지
int mid = (lo + hi)/2;
if(value < arr[mid]){
hi = mid;
}else{
lo = mid +1;
}
}
return lo;
}
}
이전 포스팅과 마찬가지로 이분 탐색법을 사용했다. 차이점은 이번 문제는 중복된 숫자가 있다는 것이다.
먼저 이분 탐색을 할 때 중요한 것은 정렬을 해야 한다는 것이다. 상근이가 가지고 있는 숫자 카드를 오름차순으로 정렬해주자.
Arrays.sort(arr);
그리고 이 문제의 핵심이라고 할 수 있는 중복된 숫자 카드를 찾는 것이다. 여기서 많은 고민을 했고 다른 분의 풀이를 보고 해결할 수 있었다.
해당 value값의 가장 작은 인덱스 값과 value값의 가장 큰 인덱스의 다음 인덱스를 반환받아서 빼면 중복된 숫자가 몇 개인지 알 수 있다.
먼저 lowerBound()를 구하는 과정을 보도록 하자.
그림에 있는 과정에서 마지막 과정이 지나고 나면 lo = 7이고 hi = 7로 둘의 값이 같아지게 된다. 그러므로 10의 가장의 작은 인덱스는 7이 반환된다. upperBound()를 구하는 과정을 보도록 하자.
lo = 10이고 hi = 10으로 둘의 값이 같아져 lo의 값이 반환된다.
sb.append(upperBound(value) - lowerBound(value).append(" ");
sb.append(10 - 7).append(" ");
sb.append(3).append(" ");
상근이가 10이 쓰여있는 숫자 카드를 3개 가지고 있는 것을 알 수 있다. 지금까지의 과정을 M만큼 반복 수행하면 주어진 M개의 숫자를 상근이가 몇 개 가지고 있는지 알 수 있다.
○ 결과
'문제풀이 > 백준' 카테고리의 다른 글
백준 1697. 숨바꼭질 (JAVA) (0) | 2022.05.19 |
---|---|
백준 1620. 나는야 포켓몬 마스터 이다솜 (0) | 2022.05.18 |
백준 1920. 수 찾기(JAVA) (0) | 2022.05.16 |
백준 7576. 토마토 (JAVA) (0) | 2022.05.03 |
백준 2178. 미로 탐색(JAVA) (0) | 2022.04.20 |