[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;
                    }
                }
            }
            }