자바(Java) 알고리즘 문제풀이 부품 찾기 [이코테 / 정렬]

 

 

 

---

 

 

 

문제 설명

동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 떄를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다.

이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성하시오.

예를 들어 가게의 부품이 총 5개일 때 부품 번호가 다음과 같다고 하자. N = 5, [8, 3, 7, 9 ,2]

손님은 총 3개의 부품이 있는지 확인을 요청했는데, 그 부품의 번호는 다음과 같다. M = 3, [5, 7, 9]

 

이때 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes, 없으면 no 를 출력하고 구분은 공백으로 한다.

 

 

 

입력 조건

첫 번째 줄에 정수 N이 주어진다. (1 <= N <= 1,000,000)

두 번째 줄에는 공백으로 구분하여 N개의 정수가 주어진다. 이때 정수는 1 ~ 1,000,000 이하이다.

세 번째 줄에는 정수 M이 주어진다. (1 <= M <= 100,000)

네 번째 줄에는 공백으로 구분하여 M개의 정수가 주어진다. 이때 정수는 1 ~ 1,000,000 이하이다.

 

 

 

출력 조건

 첫 번째 줄에 공백으로 구분하여 각 부품이 존재하면 yes, 없으면 no 를 출력한다.

 

 

풀이 코드

다량의 데이터를 순차 검색을 실시한다면 시간복잡도가 너무 많이 올라가기 때문에 이 정도의 입력을 받는 문제는 이진 탐색으로 적절하게  풀이하면 된다. 고객이 원하는 부품 번호를 타겟으로 잡고 시작점 0, 끝 점은 돌아야하는 배열인 store 의 길이만큼 잡아준다.

그리고 store[mid] 값이 타겟보다 크다면 왼쪽은 탐색할 필요가 없으므로 시작점을 mid + 1 값으로 초기화하고, 작다면 오른쪽은 탐색할 필요가 없으므로 끝점을 mid -1 값으로 초기화하면서 탐색하면 된다.

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

import java.util.Arrays;
import java.util.StringTokenizer;

public class 부품찾기 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] store = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            store[i] = Integer.parseInt(st.nextToken());
        }

        int m = Integer.parseInt(br.readLine());
        int[] customer = new int[m];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            customer[i] = Integer.parseInt(st.nextToken());
        }

        // 1. 이진 탐색 전 각 배열을 정렬한다.
        Arrays.sort(store); // [2, 3, 7, 8, 9]
        Arrays.sort(customer); // [5, 7, 9]

        // 2. customer 배열에서 원소 하나를 저장, store 배열에서 있는지 없는지 탐색한다.
        for (int i = 0; i < customer.length; i++) {
            boolean check = binarySearch(customer, store, n, i);

            if (check) {
                System.out.print("yes" + " ");
            } else {
                System.out.print("no" + " ");
            }
        }

    }

    private static boolean binarySearch(int[] customer, int[] store, int n, int i) {
        int target = customer[i];
        int start = 0;
        int end = store.length;

        while (start <= end) {
            // 목표값이 더 크면 목표값 왼쪽으로는 탐색할 필요가 없으므로 start = mid + 1
            int mid = (start + end) / 2;
            if (target > store[mid]) {
                start = mid + 1;

            } else if (target < store[mid]) {
                end = mid - 1;

            } else if (target == store[mid]){
                return true;
            }
        }
        return false;
    }
}