백준 1920: 수 찾기 / 이진 탐색(binary search)

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

시간 단축을 위해 이분 탐색 알고리즘을 이용하였다. 수를 n개 입력 받아 정수형 배열에 담은 후 Arrays.sort()로 오름차순 정렬을 해준다.

그 후 수를 입력 받아 이분 탐색 함수로 넘겨 배열 안에 있는지 판별하는 것을 m번 반복하면 된다. 

 

*이분탐색(이진탐색, binary search)

정렬되어 있는 수 들 중에서 key값을 찾으려고 할 때 가운데 있는 수(mid)와 같으면 key를 찾은 것이고, mid보다 key 값이 작으면 mid보다 왼쪽에 있는 수들 중 탐색, mid보다 크면 오른쪽에서 탐색하는 것을 반복하는 알고리즘

시간복잡도: O(logN)

 

1. 배열의 중간 인덱스를 구한다.

2. 배열 중간 인덱스에 들어있는 값과 찾으려는 값을 비교한다.

3. 찾으려는 값이 중간 값보다 작다면 배열의 왼쪽 부분을,중간 보다 크다면 배열의 오른쪽 부분을 탐색한다. 만약 중간 값과 같다면 해당 값의 인덱스를 반환한다. 

 

import java.util.*;

public class Main {

	public static void main(String[] args){
		int n, m;
		int num;
		Scanner sc = new Scanner(System.in);
		
		n=sc.nextInt();
		int arr[] = new int[n];
		
		for(int i=0; i<n; i++)
		{
			arr[i] = sc.nextInt();
		}
		Arrays.sort(arr);
		
		m = sc.nextInt();
		for(int i=0; i<m; i++) {
			num=sc.nextInt();
			System.out.println(search(arr, num));
		}
		
	}
	public static int search(int arr[], int n) {
		int l=0, r= arr.length - 1;
		int m;
		while(l<=r) {
			m=(l+r)/2;
			if(n==arr[m])
				return 1;
			if(n<arr[m])
				r=m-1;
			else
				l=m+1;
			
		}
		
		return 0;
	}
}

 

몰랐는데 java.util.Arrays 클래스에는 이진 탐색 함수가 있다.

key 값이 있으면 위치하는 자리의 인덱스를 반환하고, 없으면 key보다 최초로 큰 수가 있는 자리의 인덱스에 -1을 곱한 후 -1을 한 값을 반환한다.

 

해당 api 메소드를 이용하여 문제를 풀어보았다.

import java.util.*;

public class Main {

	public static void main(String[] args){
		int n, m;
		int num;
		Scanner sc = new Scanner(System.in);
		
		n=sc.nextInt();
		int arr[] = new int[n];
		
		for(int i=0; i<n; i++)
		{
			arr[i] = sc.nextInt();
		}
		Arrays.sort(arr);
		
		m = sc.nextInt();
		for(int i=0; i<m; i++) {
			num=sc.nextInt();
			if(Arrays.binarySearch(arr, num)>=0)
				System.out.println("1");
			else
				System.out.println("0");
		}	
	}
}

코드는 훨씬 짧아지지만 위처럼 직접 함수를 구현한 쪽이 처리 시간은 빠르다.