백준
백준 1920: 수 찾기(java)
unhyepnhj
2024. 7. 18. 21:17
문제

풀이
아래와 같이 비교하는 코드로는 시간 초과 에러가 표시된다. 컬렉션과 contains()를 사용하지 않고 배열 2개로 순차 비교하는 방법도 마찬가지다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Vector;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int N=Integer.parseInt(br.readLine());
String[] arrN=br.readLine().split(" ");
int M=Integer.parseInt(br.readLine());
String[] arrM=br.readLine().split(" ");
Vector<Integer> vector=new Vector<>();
for(int i=0; i<N; i++)
vector.add(Integer.parseInt(arrN[i]));
for(int i=0; i<M; i++) {
if(vector.contains(Integer.parseInt(arrM[i])))
System.out.println(1);
else
System.out.println(0);
}
}
}

효율적인 탐색을 진행해야 시간 제한 조건에 맞게 풀 수 있는 문제이다.
이분 탐색의 시간 복잡도는 O(nlogn)이므로 이분 탐색을 이용하여 풀면 효과적인 풀이가 가능하다.
이분 탐색 알고리즘을 직접 구현하기보다는 기본 제공되는 Arrays.binarySearch()를 사용했다.

for(int i=0; i<M; i++) {
if(Arrays.binarySearch(arrN, arrM[i])<0)
System.out.println(0);
else
System.out.println(1);
}
목표하는 값이 존재하지 않을 경우 -1을 반환하고, 존재할 경우 해당 값의 인덱스를 반환하므로 이분 탐색 결과가 -1일 때와 아닐 때로 경우를 나누어 작성하면 된다.
전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Vector;
public class Main {
public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int N=Integer.parseInt(br.readLine());
String[] arrN=br.readLine().split(" ");
Arrays.sort(arrN);
int M=Integer.parseInt(br.readLine());
String[] arrM=br.readLine().split(" ");
for(int i=0; i<M; i++) {
if(Arrays.binarySearch(arrN, arrM[i])<0)
System.out.println(0);
else
System.out.println(1);
}
}
}