백준

백준 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);
		}
	}
}