이번 문제는 입력에서 하단에 받은 값이 상단에 있는지 확인해서 있으면 1 없으면 0을 출력해야 하는데, 다른 문제들처럼 구현만 하면 해결되는 것이 아니라 자연수 범위가 매우 넓기 때문에, 시간 제한에 걸리지 않기 위해서 빨리 구현해야 할 필요가 있는데 이진 탐색을 모르면 진행이 불가능하기 때문에 반드시 개념을 알아두고 진행해야 한다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int count = Integer.parseInt(br.readLine());
String[] split = br.readLine().split(" ");
int[] searchArr = new int[split.length];
for (int i = 0; i < split.length; i++) {
searchArr[i] = Integer.parseInt(split[i]);
}
Arrays.sort(searchArr);
br.readLine();
String[] split2 = br.readLine().split(" ");
int[] mainArr = new int[split2.length];
for (int i = 0; i < split2.length; i++) {
mainArr[i] = Integer.parseInt(split2[i]);
}
for (int i = 0; i < mainArr.length; i++) {
if (Arrays.binarySearch(searchArr, mainArr[i]) > -1) {
System.out.println(1);
} else {
System.out.println(0);
}
}
}
}문제 자체는 먼저 입력받은 내용으로 배열을 만들되, 이 배열을 가지고 이진 탐색을 진행하기 위해 Arrays.sort() 메소드로 정렬을 해두고 두 번째 입력받는 내용으로 배열을 만든 뒤
하나씩 돌려주면서 이진 탐색을 진행해주면 되는데, 원리를 모르면 이진 탐색 메소드를 만들면서 진행을 하는 것이 좋겠지만 원리를 알고 있다면 그 다음부터는 시간 싸움이기 때문에
굳이 구현할 필요 없이 Arrays.binarySearch(배열, 찾을_값); 을 사용해주면 값이 있을 경우 해당 값의 인덱스를 리턴 받을 수 있고 없다면 음수를 받게 되는데 값을 확인한 뒤 있으면 1 없으면 0을 출력하면 끝이다.
Leave a Reply