○ 문제 요약
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());
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());
StringBuilder sb = new StringBuilder();
st = new StringTokenizer(br.readLine());
for(int i = 0 ; i < M ; i++){
if(BinarySearch(Integer.parseInt(st.nextToken()))>=0){
sb.append(1).append('\n');
}else{
sb.append(0).append('\n');
}
}
System.out.println(sb);
}
public static int BinarySearch(int value){
int lo = 0;
int hi = arr.length -1;
while(lo <= hi){
int mid = (lo + hi)/2;
if(value < arr[mid]){
hi = mid - 1;
}else if(value > arr[mid]){
lo = mid + 1;
}else{
return mid;
}
}
return -1;
}
}
처음으로 이분 탐색법을 사용해서 문제를 해결했다. 이분 탐색법에 대한 내용은 추후에 정리해서 올릴 예정이다.
이 문제를 풀면서 이분 탐색법의 핵심은 계속 반으로 분할해서 정하는 값을 찾는 것이다. 그래서 BinarySearch 메서드를 보면 찾고 싶은 값을 기준으로 찾고 싶은 배열의 인덱스를 조정해가면서 값을 비교하는 것을 알 수 있다.
예제 입력을 예로 설명해보면
4 | 1 | 5 | 2 | 3 |
arr 배열은 위처럼 값이 들어있고 추가적으로 배열은 생성하지 않고 입력받는 대로 사용했다.
이분 탐색법을 할 때, 반드시 배열을 정렬해주어야 한다. 정렬을 깜박하고 출력을 했을 때 전혀 다른 값이 나온다. 그러므로 이 점 유의하도록 하자!
arr 배열에 value 값이 포함되어 있는지 확인하기 위해 arr의 중간 index를 구해주고 그 index의 값이 value의 값과 같은지 비교한다. 만약에 value의 값이 더 작다면 hi = mid - 1을 해서 더 작은 index값과 비교할 수 있도록 해준다. 반대로 value의 값이 더 크다면 lo = mid + 1을 해서 더 큰 index값과 비교할 수 있도록 해준다. 그래서 index 값과 value 값이 같다면 그 index값을 반환해준다.
이 과정을 M만큼 반복 수행하면 원하는 값을 출력할 수 있다.
○ 결과
'문제풀이 > 백준' 카테고리의 다른 글
백준 1620. 나는야 포켓몬 마스터 이다솜 (0) | 2022.05.18 |
---|---|
백준 10816. 숫자 카드2 (JAVA) (0) | 2022.05.17 |
백준 7576. 토마토 (JAVA) (0) | 2022.05.03 |
백준 2178. 미로 탐색(JAVA) (0) | 2022.04.20 |
백준 9372. 상근이의 여행(JAVA) (0) | 2022.04.18 |