[이진 탐색] 문제 이름 : 부품 찾기 - 배열 Sort, Binary Search

문제 설명

가게의 부품이 총 5개일 때 부품 번호가 다음과 같다고 하자.

N = 5

[8, 3, 7, 9, 2]

손님은 총 3개의 부품이 있는지 확인 요청했는데 부품 번호는 다음과 같다.

M = 3

[5, 7, 9]

이때 가게 안에 손님이 원하는 부품이 모두 있는지 확인하는 프로그램을 작성해보자.

사용 개념

탐색

문제 해결 아이디어

비교 대상이 되는 값들을(가게의 부품 번호) 배열에 저장하므로, java.util.Arrays 에서 제공하는 sort()로 정렬하고, binarySearch() 사용하여 탐색함

코드

import java.util.Arrays;
import java.util.Scanner;

public class Q1 {    
    public static void main(String[] args) {
        Scanner kbd = new Scanner(System.in);

        int numOfExist = kbd.nextInt();    // 존재하는 부품의 개수 
        int[] exist = new int[numOfExist];    // 존재하는 부품 번호 

        for(int i = 0; i < numOfExist; i++) {
            exist[i] = kbd.nextInt();
        }

        int numOfWant = kbd.nextInt();    // 요청 부품 개수 
        int[] want = new int[numOfWant];    // 요청 부품 번호 

        for(int i = 0; i < numOfWant; i++) {
            want[i] = kbd.nextInt();
        }

        Arrays.sort(exist);    // ㄱ. Sorting 

        for(int i = 0; i < numOfWant; i++) {
            int check = Arrays.binarySearch(exist, want[i]);    // exist: array to be searched, want[i]: value to be searched for 

            if(check >= 0) // 존재할 때 
                System.out.print("yes ");
            else    
                System.out.print("no ");
        }
    }
}

ㄱ. Sorting
java.util.Arrays의 static int binarySearch​(int[] a, int key) 의 인자로 들어가는 배열은 정렬된 값들이어야 하므로 static void sort​(int[] a) 으로 오름차순 정렬함

추가 개념 정리

java.util.Arrays의 static int binarySearch​(int[] a, int key)

// Arrays.class 에 작성되어 있는 코드 
    private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                     int key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;    // Shift Right ((low+high)/2 와 동일한 의미);
            int midVal = a[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }

→ 반복문으로 구현된 이진 탐색