알고리즘 풀이(JAVA) - [이분 탐색] 백준 알고리즘(수 찾기)

By on October 1, 2019

문제

문제 링크 : 이분탐색-수 찾기 https://www.acmicpc.net/problem/1920

이분탐색 수 찾기 문제

풀이

  • 이 문제를 풀기 전에 이분탐색에 대해서 알아보자.

  • 이 문제는 이분 탐색을 알면 쉽게 풀 수 있다.

    • 숫자들의 집합 (aLen)
    • 찾아야 되는 숫자의 집합 (bLen)
    • 이분탐색은 정렬되어있는 배열 에서 찾는 탐색 방법으로 aLen을 오름 차순으로 정렬한다.
    • bLen 의 숫자를 하나씩 가져와 이분탐색으로 숫자들의 집합(aLen) 에서 존재 유무를 찾는다.

소스

  • 수 찾기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Backjoon_1920 {
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		
        //입력 처리 ------------------------------------------------
		int aLen = Integer.parseInt(reader.readLine());
		String[] inputArrA = reader.readLine().split(" ");
		int bLen = Integer.parseInt(reader.readLine());
		String[] inputArrB = reader.readLine().split(" ");
		
		int[] arr = new int[aLen];
		int[] findNums = new int[bLen];
		
		for (int i = 0; i < inputArrA.length; i++) {
			arr[i] = Integer.parseInt(inputArrA[i]);
		}
		for (int i = 0; i < inputArrB.length; i++) {
			findNums[i] = Integer.parseInt(inputArrB[i]);
		}
        //----------------------------------------------------------		

        //정렬
		Arrays.sort(arr);
        
        //탐색 & 출력
		for (int num : findNums) {
			System.out.println(find(arr, 0, arr.length - 1, num));
		}
	}
	
    //탐색 재귀 함수
	private static int find(int[] arr, int left, int right, int num) {
		int index = (left + right) / 2;
		if(left > right) {
			return 0 ;
		}
		if(arr[index] == num) {
			return 1;
		}
		if(arr[index] > num) {
			return find(arr, left, index - 1, num);
		}else {
			return find(arr, index + 1, right, num);
		}
	}
}

Back to blog