[백준 10815: JAVA] 숫자 카드 / 이분 탐색

개요

 

기본적인 이분 탐색을 이용하면 풀이할 수 있다.

일반적으로 이분탐색을 모르면 for문을 끝까지 돌려서 찾으려 할 것이다.

그러나 그렇게 하면 이 문제의 경우 최대 (500,000 * 20,000,000) 번 탐색을 하게 된다.

시간 초과가 발생하기 때문에 이분 탐색을 이용하면 더 빠르게 찾을 수 있다.

 

문제

 

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

 

입력

 

풀이

 

이분탐색을 위해 정렬을 진행하고 나면 arr배열에는 아래와 같이 데이터가 정렬이 된다.

문제에서 찾고자 하는 숫자를 num이라고 한다면,

1. 초기 값으로 left = 0, right = n을 저장한다.

2. mid는 left와 right의 중간값으로 설정한다.

3. arr[mid] 와 num을 비교한다.

• arr[mid] > num 인 경우 ▶ left = left + 1을 하고 2~3을 반복한다.
• arr[mid] < num 인 경우 ▶ right = right - 1을 하고 2~3을 반복한다.
• arr[mid] == num 인 경우 ▶ num을 찾은 것이므로 반복을 종료한다.

4. num을 찾지 못하고 반복문이 종료된 경우 찾지 못한 것이다.

 

 

코드

 

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int n, m;
    static int arr[];

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i = 0 ; i < n; i++)
            arr[i] = Integer.parseInt(st.nextToken());

        // 숫자 카드 오름차순 정렬
        Arrays.sort(arr);

        m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        for(int i = 0 ; i < m; i++) {
            int num = Integer.parseInt(st.nextToken());
            // 이분 탐색을 해서 해당 숫자가 있는 경우
            if(binarySearch(num)) bw.write("1 ");
            // 이분 탐색을 해서 해당 숫자가 없는 경우
            else bw.write("0 ");
        }

        bw.close();
        br.close();
    }
    private static boolean binarySearch(int num) {
        int leftIndex = 0;
        int rightIndex = n - 1;

        while(leftIndex <= rightIndex){
            int midIndex = (leftIndex + rightIndex) / 2;
            int mid = arr[midIndex];

            if(num < mid) rightIndex = midIndex - 1;
            else if(num > mid) leftIndex = midIndex + 1;
            else return true;
        }
        return false;
    }
}