[Algorithm] 이것이 코딩테스트다 - 이진탐색 문제풀이(with 자바)

부품찾기

public class 부품찾기 {
    public static void main(String [] args){
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[] parts = new int[N];
        for(int i=0; i<N; i++) parts[i] = scanner.nextInt();

        int M = scanner.nextInt();
        int[] selectedParts = new int[M];
        for(int i=0; i<M; i++) selectedParts[i] = scanner.nextInt();

        부품찾기 bs = new 부품찾기();
        bs.binarySearch(parts, selectedParts);
    }

    public void binarySearch(int[] parts, int[] selectParts){
        //탐색을 원하는 부품 반복
        Arrays.stream(selectParts)
                .forEach(x-> {
                    int target = x;
                    int start = 0;
                    int end = selectParts.length;
                    boolean isYes = false;

                    //이진 탐색으로 부품 존재 확인
                    while(start <= end){
                        int mid = (start + end) / 2;
                        if(target == selectParts[mid]){
                            System.out.print("yes ");
                            isYes = true;
                            break;
                        }else if(target < parts[mid]){
                            end = mid - 1;
                        }else{
                            start = mid + 1;
                        }
                    }
                    if(!isYes) System.out.print("no ");
                });
    }
}

 

떡볶이만들기

· 이진 탐색 문제이자 파라메트릭서치(Parametric search) 유형인 문제

· 파라메트릭처리: 최적화 문제를 결정 문제('네' 또는 '아니오'로 답하는 문제)로 바꾸어 해결하는 기법

   - 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제에 주로 사용

· 코딩 테스트에서 보통 파라메트릭 서치 유형은 이진 탐색을 이용하여 해결

public class 떡볶이떡만들기 {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int N, M; //떡의 개수, 요청한 떡의 길이
        N = scanner.nextInt();
        M = scanner.nextInt();

        List<Integer> lengthList = new ArrayList<>(); // 떡들의 길이
        for(int i=0; i <N ; i++) {
            Integer num = scanner.nextInt();
            lengthList.add(num);
        }

        lengthList.sort(Comparator.naturalOrder());
        int end = lengthList.get(lengthList.size()-1);
        int start = 0;
        binarySearch(start,end,M,lengthList);
    }

    static void binarySearch(int start , int end, int target, List<Integer> lengthList){
        while(start <= end){
            int mid = (start+end)/2; // 절단기 길이 구하기
            // 자르고 남은 떡의 길이
            int remainder = lengthList.stream()
                    .filter(length -> length>mid) //절단기 보다 짧은 떡을 제거하고,
                    .mapToInt(x->x%mid) //절단기로 자른 떡들의 길이를 매핑하여,
                    .sum(); //더한다.

            if(remainder == target) {
                System.out.println(mid);
                break;
            }else if(remainder > target){
                start = mid+1;
            } else {
                end = mid-1;
            }
        }
    }
}