[백준] 1920번 - 수 찾기

 

1920번: 수 찾기

 

 

이분 탐색의 기본 개념에 대해 이해하기 좋은 문제이다. 

 

이분 탐색이란 어떤 문제를 해결하기 위한 일련의 판단이 YES or NO 판단의 연속인 문제를 말한다. 이 문제의 경우를 예로들어보자.

N개의 정수가 주어지고 이 안에 정수  X가 존재하는지 알아보고자 한다. N개의 정수를 일일이 비교하여 X가 존재하는지 확인하는 방법을 사용할 수도 있겠지만 이분 탐색을 적용해볼 수 있다. 

 

이분 탐색을 위해서는 반드시 탐색하는 수열이 정렬되어 있어야 한다. N개의 정수를 담고 있는 배열을 A라고 할 때, 오름차순 정렬된 A에서 순서상으로 중간에 위치한 요소의 값 A[mid]이 찾고자 하나는 정수인 X와 같다면 X는 N개의 정수에 존재하는 것이다. 그렇지 않다면 A[mid]와 찾고자 하는 값인 X의 크기를 비교하여 A[mid]가 X보다 작다면 다음 이분 탐색할 범위의 최소 인덱스를 mid + 1로 하고, A[mid]가 X보다 크다면 다음 이분 탐색할 범위의 최대 인덱스를 mid - 1로 하고, 이전의 과정을 반복한다. 이렇게 탐색을 진행한다면 한 사이클에 탐색할 범위가 절반씩 줄어들게 된다.

 

위 일련의 과정을 left <= right (left = 탐색 범위의 최소 인덱스, right = 탐색 범위의 최대 인덱스)라면 반복해준다. 반복하는 도중에 X와 매칭되는 값이 A에 존재한다면 left <= right인 상태로 반복문이 종료 될 것이기 때문에 반복문 이후에 left <= right라면 1을 출력, left > right 라면 0을 출력한다.

left = 0;
right = N-1;

while (left <= right) {
    int mid = (left + right) / 2;

    if (A[mid] == B[i]) break;
    else if (A[mid] < B[i]) left = mid + 1;
    else if (A[mid] > B[i]) right = mid - 1;
}

if (left <= right) sb.append(1 + "\n");
else sb.append(0 + "\n");

 

이분 탐색을 사용하는 이유는 속도면에서 장점을 갖기 때문이다.

만약 주어진 수열에서 숫자 단 1개만 찾으려고 한다면 정렬하는 과정을 거치지 않고 순차적으로 값을 비교하는 것이 더 빠를 수도 있지만 이 문제의 경우 찾고자 하는 수의 갯수가 최대 100,000개이다. 이분 탐색으로 중간 값과 찾고자 하는 값의 크기를 비교하며 1cycle마다 탐색 범위를 절반으로 줄인다면 비교하는 횟수를 줄일 수 있기 때문에 주어진 수열을 최초 정렬하여 재사용 한다면 전체 M개의 수에 대한 탐색시간은 줄어들 것이다.

 

이를 시간 복잡도 관점에서 비교해보자.

길이가 N인 수열에서 M개의 수에 대한 완전 탐색을 사용한다면 수열 길이가 늘어나는 만큼 탐색할 범위도 선형적으로 증가하므로 N*M의 시간복잡도를 갖겠지만, 이분 탐색을 사용한다면 정렬하는데 NlogN 와 M개의 수에 대한 탐색으로 MlogN을 합친 NlogN + MlogN = (N+M)logN의 시간 복잡도를 갖는다. 

 

이런 이분 탐색의 특성 때문에 탐색 범위가 길어지면 길어질 수록, 동일한 수열에서 수를 찾는 횟수가 많으질 수록 이분 탐색의 장점은 빛을 발한다.

 

 

 

전체 코드

import java.util.*;

public class Main {
    
    public static void main (String[] args) {
        
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        
        int N = Integer.parseInt(sc.nextLine());
        int[] A = new int[N];
        
        
        StringTokenizer st = new StringTokenizer(sc.nextLine());
        for (int i=0; i<N; i++) A[i] = Integer.parseInt(st.nextToken());
        
        Arrays.sort(A);
        
        
        int M = Integer.parseInt(sc.nextLine());
        int[] B = new int[M];
        
        
        st = new StringTokenizer(sc.nextLine());
        for (int i=0; i<M; i++) B[i] = Integer.parseInt(st.nextToken());
        
        
        
        for (int i=0; i<M; i++) {
            
            int left = 0;
            int right = N-1;
            
            // left <= right 라면 탐색 계속
            while (left <= right) {
                
                // 현재 탐색 범위의 중간 값
                int mid = (left + right) / 2;
            
                if (A[mid] == B[i]) break; // 찾고자 하는 값 찾음(left <= right 상태로 반복문 종료)
                else if (A[mid] < B[i]) left = mid + 1; // 다음 탐색 범위의 시작을 mid+1
                else if (A[mid] > B[i]) right = mid - 1; // 다음 탐색 범위의 끝을 mid-1
            }
            
            if (left <= right) sb.append(1 + "\n");
            else sb.append(0 + "\n");
        }
        
        System.out.println(sb);
        
        sc.close();
    }
}