문제 내용은 입력으로 상근이가 가지고 있는 숫자 카드를 받은 뒤, 상근이가 있는지 판별해야 하는 숫자 카드를 한번 더 받고 마지막에 받은 숫자 카드를 기준으로 상근이가 가지고 있으면 1 아니면 0을 출력해줘야 하는데 문제를 보면 입력 범위가 굉장히 넓기 때문에 배열이나 List를 이용한 단순 조회로는 시간이 부족하므로 이걸 고려해서 풀어줘야 한다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
public static int binarySearch(int arr[], int t) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == t) {
return mid;
} else if (arr[mid] < t) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
br.readLine();
int[] sangArr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
Arrays.sort(sangArr);
br.readLine();
int[] checkArr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
StringBuilder sb = new StringBuilder();
for (int check : checkArr) {
if (binarySearch(sangArr, check) > -1) {
sb.append("1 ");
} else {
sb.append("0 ");
}
}
System.out.println(sb.substring(0, sb.length() - 1));
}
}문제를 풀어보자면 결국 많은 범위의 수를 빠르게 찾아줘야 하기 때문에 이진 탐색을 사용해줘야 하는데 이진 탐색이란 찾아야 하는 범위를 계속 줄여 나가는 방법인데 1~10까지의 수 중 3을 찾아야 한다면 일단 중간 값인 1~5까지만 남기고 이후 찾아야 하는 값이 중간 인덱스의 값보다 크면 줄이고, 작으면 늘리는 식으로 범위를 계속 좁혀 나가서 찾아주면 되는데
이진 탐색의 개념을 이해하고 있다면 수작업으로 메소드를 작성할 필요 없이, Arrays.BinarySearch(배열, 찾는_값) 을 사용해주면 찾았다면 해당 값의 인덱스, 찾지 못했다면 음수를 반환하므로 이 메소드를 사용해서 해결해줘도 된다.
Leave a Reply