[JAVA] 백준 4158_CD

https://www.acmicpc.net/problem/4158

백준 4158 CD 문제

📌 문제 탐색하기

이분탐색 문제 유형.
두 배열에서 공통된 원소의 개수를 출력하는 문제이다. CD 번호들이 정렬된 상태로 들어오기때문에 이분탐색을 이용하면 효율적으로 풀 수 있다.

📌 가능한 시간복잡도

이분탐색을 이용한 효율적인 문제 풀이~
선영이의 CD 한개당 O(log N) 으로 처리가 가능하기 때문에 입력받는 선영이의 CD 개수 M개 ...
전체 시간 복잡도는 O(log  N * M ) 입니다.  

📌 코드 설계하기

상금이의 CD리스트를 중심으로 선영이의 CD번호를 하나씩 이분 탐색해서 상근이가 가지고 있는 체크하기

📌 정답 코드

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

public class Main {
    
    public static boolean binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (arr[mid] == target) return true;
            else if (arr[mid] < target) left = mid + 1;
            else right = mid - 1;
        }

        return false;
    }
    
   
    public static void main(String[] args) throws IOException {
        //Scanner sc = new Scanner(System.in);
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       StringTokenizer st;
        
        while (true) {
            st = new StringTokenizer(br.readLine());
             int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            //int N = sc.nextInt(); 
            //int M = sc.nextInt(); 
            if (N == 0 && M == 0) break;

            int[] sang = new int[N];
            for (int i = 0; i < N; i++) {
                //sang[i] = sc.nextInt();
                sang[i] = Integer.parseInt(br.readLine());
            }
            int count = 0;
            for (int i = 0; i < M; i++) {
                //int cd = sc.nextInt();
                int cd = Integer.parseInt(br.readLine());
                if (binarySearch(sang, cd)) count++;
            }
            System.out.println(count);
        }
    }
}