[이진 탐색] 이코테 부품 찾기(Java)

📚 문제

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

N=5
[8, 3, 7, 9, 2]

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

M=3
[5, 7, 9]

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

 

📝 문제 해결

이진 탐색

import java.util.*;

public class search08 {

    public static int binarySearch(int[] arr, int target, int start, int end) {
        while (start <= end) {
            int mid = (start + end) / 2;
            if (arr[mid] == target) return mid;	// 찾은 경우 중간점 인덱스 반환
            else if (arr[mid] > target) end = mid - 1;	// 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
            else start = mid + 1;	// 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
        }
        return -1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        Arrays.sort(arr);

        int m = sc.nextInt();
        int[] targets = new int[m];
        for (int i = 0; i < m; i++) {
            targets[i] = sc.nextInt();
        }

        for (int i = 0; i < m; i++) {
            int result = binarySearch(arr, targets[i], 0, n - 1);
            if (result != -1) {
                System.out.print("yes ");
            }
            else {
                System.out.print("no ");
            }
        }
    }

}

 

계수 정렬

모든 원소의 번호를 포함할 수 있는 리스트를 만든 뒤, 리스트의 인덱스에 직접 접근하여 해당 값이 존재하는지 확인

import java.io.*;
import java.util.*;

public class search09 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int[] arr = new int[1000001];
		for(int i=0; i<n; i++) {
			int x = sc.nextInt();
			arr[x] = 1;
		}
		
		int m = sc.nextInt();
		int[] targets = new int[n];
		for(int i=0; i<m; i++) {
			targets[i] = sc.nextInt();
		}
		
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<m; i++) {
			if(arr[targets[i]]==1) {
				sb.append("yes").append(" ");
			}else {
				sb.append("no").append(" ");
			}
		}
		
		System.out.println(sb);
	}
}

 

집합 자료형

특정한 수가 한 번이라도 등장했는지를 검사하면 되므로 집합 자료형을 이용해서 문제를 해결할 수 있다.

import java.util.*;

public class search10 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		HashSet<Integer> s = new HashSet<>();
        for (int i = 0; i < n; i++) {
                int x = sc.nextInt();
                s.add(x);
            }
		
		int m = sc.nextInt();
		int[] targets = new int[1000001];
		for(int i=0; i<m; i++) {
			targets[i] = sc.nextInt();
		}
		
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<m; i++) {
			if(s.contains(targets[i])) {
				sb.append("yes ");
			}else {
				sb.append("no ");
			}
		}
		
		System.out.println(sb);
	}
}

집합 자료형은 단순히 특정한 데이터가 존재하는지 검사할 때에 매우 효과적으로 사용할 수 있다.