[알고리즘-자바] 백준 1920번 수 찾기

 

문제

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

1920번: 수 찾기

언어

자바 JAVA

로직

이진탐색트리 사용

전체 코드

이진탐색트리를 사용하였다. 이진탐색트리란 배열에서 검색해야 하는 범위를 절반씩 줄여나가면서 원하는 값을 찾는 방법이다. 배열을 처음부터 끝까지 모두 탐색하는 것보다 절반씩 줄여나가면서 찾는 것이 훨씬 빠르다.

최악의 경우를 예로 들자면, 배열의 요소가 10만개가 존재하는데 0번 인덱스부터 탐색한다고 생각해 봐라. 게다가 찾고자 하는 값이 배열의 마지막 인덱스에 위치해 있다면 얼마나 오래 걸릴지 예상이 될 것이다.

주의할 점은 배열을 반드시 오름차순으로 정렬을 진행하고 이진탐색을 시작해야 한다.

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

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();

        int n = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");
        int[] a = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(input[i]);
        }
        // 반드시 배열을 정렬한다.
        Arrays.sort(a);

        int m = Integer.parseInt(br.readLine());
        input = br.readLine().split(" ");

        for(int i = 0; i < m; i++) {
            sb.append(binarySearch(0, n - 1, Integer.parseInt(input[i]), a) + "\n");
        }

        System.out.println(sb);
    }

    // 이진 탐색 트리, 재귀함수
    static int binarySearch(int start, int end, int find, int[] arr) {
        // 시작과 끝의 중간지점을 구한다.
        int mid = (start + end) / 2;

        // IF문 조건 필수!
        if(start <= end) {
            // 값을 찾았다면 반환
            if(arr[mid] == find) {
                return 1;
            }
            // 중간값 > 찾는값 : 끝 위치를 앞당겨 검색 범위를 절반으로 줄인다.
            else if(arr[mid] > find) {
                return binarySearch(start, mid - 1, find, arr);
            }
            // 중간값 < 찾는값 : 시작 위치를 뒤로 땡겨 검색 범위를 절반으로 줄인다.
            else {
                return binarySearch(mid + 1, end, find, arr);
            }
        }

        // 시작 위치 > 끝 위치 : 배열에 찾고자 하는 값이 없다
        return 0;
    }
}

 

또 하나 주의할 점은 if문 조건이 반드시 있어야한다. if문 조건이 없으면 요소의 인덱스를 벗어나는 상황을 만나게 된다.

아래 사진을 보자. 1, 3, 5, 7, 9 요소가 담겨있는 배열이 있다. 내가 찾고자 하는 값은 4이다. 당연히 4는 배열에 존재하지 않는다. 첫 번째 이진탐색 결과 1, 3 요소만 남게 된다. 다음으로 두번째 이진탐색 결과 3 요소만 남게된다. 아직 우리는 찾는 값 4를 발견하지 못했으므로 이진탐색을 한 번 더 수행한다. 그러나 여기서 예외가 터진다. 탐색 시작 위치(start)가 배열의 범위를 벗어났다.  

따라서 if문 조건을 반드시 사용해야 한다.

(실제로는 사진과 같이 배열의 길이가 줄어들지 않는다. 이해를 돕기 위해서 배열의 길이를 줄여가며 설명한다.)