[이분탐색] 백준 - 수 찾기

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

1920번: 수 찾기

 

-문제해설

기본적인 이분탐색 문제로 주어진 배열에서 찾으려는 값이 있는지 탐색하는 문제이다.

 

찾으려는 값을 target = 1이라고 하고 주어진 배열을 arr = {1, 2, 3, 4, 5}라고 하자.

주어진 배열 arr 에서 첫 번째 인덱스를 start, 끝 인덱스를 end로 하고
중간 인덱스인 (start+end)/2 = 2를 mid로 선언한다.

 

그리고 arr[mid]가 target보다 크면 ( arr[mid] > target  ==>  3 > 1 ) 이면
end = mid - 1 = 2-1 = 1로 초기화하고 다시 mid값을 구한다. mid = (start+end)/2 = ( 0+1 ) / 2 = 0

 

다시 arr[mid] > target 를 비교했더니 1 == 1 이므로 해당 값이 존재하니깐 반복문을 빠져나오고 1을 리턴해준다.

만약에 존재하지 않을 경우 0을 리턴한다.

 

 

이분탐색말고도 찾아보니깐 해쉬맵의 키값으로도 해결할 수 있는 문제이다. 해쉬맵이 훨씬 효율적이다.

문제조건에는 중복되지 않는다. 라는 말이 없지만 데이터값에 중복이 없으므로 해쉬맵의 키값이 겹칠 일이 없다.

키 값에 a배열 값들을 모두 넣고 특정 키가 존재여부를 알려주는 .containsKey() 메서드를 사용하면 된다.

 

파이썬도 자바의 hashmap과 비슷하게 풀었다. 파이썬에서는 in, not in기능이 있어서 이를 활용하면 쉽게 풀 수 있다.

 

 

-자바( 이분탐색 )

package search;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BJ1920 {
	
	private static int Search( int[] arr, int target, int start, int end ) {
		int a = 0;
		
		while( start <= end ) {
			if( start == end && arr[start] != target ) break;
			int mid = (start+end)/2;
			
			if( arr[mid] == target ) {
				a = 1; 
				break;
			} else if( arr[mid] < target ) start = mid + 1;
			else end = mid - 1;
		}
		
		return a;
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int n = Integer.parseInt( br.readLine() );
		int[] arr = new int[n];
		st = new StringTokenizer( br.readLine() );
		for( int i=0; i<n; i++ ) arr[i] = Integer.parseInt( st.nextToken() );
		
		int m = Integer.parseInt( br.readLine() );
		int[] brr = new int[m];
		st = new StringTokenizer( br.readLine() );
		for( int i=0; i<m; i++ ) brr[i] = Integer.parseInt( st.nextToken() );
		
		//arr 배열 오름차순 정렬
		Arrays.sort( arr );
		
		StringBuffer sb = new StringBuffer();
		for( int i=0; i<brr.length; i++ ) 
			sb.append( Search( arr, brr[i], 0, arr.length-1 )+"\n" );
		System.out.println( sb );
	}
}

 

-자바( 해쉬맵 이용 )

package search;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class BJ1920_1 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		HashMap<String, Integer> hm = new HashMap<String, Integer>();
		
		int n = Integer.parseInt( br.readLine() );
		st = new StringTokenizer( br.readLine() );
		for( int i=0; i<n; i++ ) hm.put( st.nextToken(), 0 );
		
		int m = Integer.parseInt( br.readLine() );
		String[] marr = new String[m];
		st = new StringTokenizer( br.readLine() );
		for( int i=0; i<m; i++ ) marr[i] = st.nextToken();
		
		StringBuffer sb = new StringBuffer();
		for( String s : marr ) {
			if( hm.containsKey( s ) ) sb.append( "1\n" );
			else sb.append( "0\n" );
		}
		System.out.println( sb );
	}
}

 

 

-파이썬

import sys
readline = sys.stdin.readline

n = int( readline() )
A = set( readline().split() )
m = int( readline() )

ans = ""
for i in readline().split():
    if i in A: ans += "1\n"
    else: ans += "0\n" 
print( ans )