99클럽 코테 스터디 20일차 TIL + 백준 4158 (CD, java)

 

오늘의 학습 키워드

• 이분탐색

 

문제 탐색하기

 

문제 풀이 설계하기

이분 탐색으로 문제 풀이를 진행했습니다.

 

코드

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

public class Main{
    private static ArrayList<Integer> result = new ArrayList<>();
    private static int[] cd1;

    public static void main(String []args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while(true){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            if(N == 0 && M == 0) break;

            cd1 = new int[N];
            for(int i=0; i<N; i++){
                cd1[i] = Integer.parseInt(br.readLine());
            }
            Arrays.sort(cd1);

            int[] cd2 = new int[M];
            int cnt = 0;
            for(int i=0; i<M; i++){
                cd2[i] = Integer.parseInt(br.readLine());
                cnt += binarySearch(cd2[i]);
            }

            result.add(cnt);
        }

        for(int cdCnt : result){
            System.out.println(cdCnt);
        }
    }

    public static int binarySearch(int target){
        int left = 0;
        int right = cd1.length - 1;

        while(left <= right){ // 종료 조건 수정 (optional)
            int mid = (left + right) / 2;

            if(cd1[mid] == target){
                return 1;
            } else if(cd1[mid] > target){
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return 0;
    }
}

 

오늘의 회고

이분탐색에 대해 익숙해지고 있는 것 같습니다.