백준 1920번: 수 찾기 [이분탐색][정렬] - Java

 

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

1920번: 수 찾기

이분 탐색 알고리즘의 가장 기초적인 문제.

start, end 범위를 정하고  /2 를 통해 범위를 좁혀가면서 찾는다.

 

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

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		
		//System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		
		int N = Integer.parseInt(st.nextToken());
		int arr[] = new int[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(arr);
		
		st = new StringTokenizer(br.readLine());
		int M = Integer.parseInt(st.nextToken());
		
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < M; i++) {
			int num = Integer.parseInt(st.nextToken());
//			System.out.println(num);
			int res = 0;
			int l = 0;
			int r = N-1;
			while(l <= r) {
				
				int m = (l+r)/2;
				if(arr[m] < num ) l = m+1;
				else if (num < arr[m]) r = m-1;
				else {
					res = 1;
					break;
				}
			}
			
			System.out.println(res);
		}
	}

}

굳이 정렬하지 않고, 범위도 나누기 싫다면 HashSet을 쓰게되면 중복제거&오름차순으로 자동 정렬이 된다.

set의 contains() 함수활용.

 

728x90

 

위와 같은 이분탐색은 Arrays안에 메소드가 존재한다. 굳이 수동으로 알고리즘 구현하지 않고 아래와 같은 메소드를 사용해도 된다.

Arrays.binarySearch() 

 

int idx = Arrasy.binarySearch(arr, x); //x는 조사하려는 값.

//arr안에 x가 존재한다면 해당 index를 return해준다.

(idx가 없다면 -1 리턴됨)