자바 [Algorithm] 이분탐색 - 백준 4158 CD

1. 문제

2. 접근법

1. 예제 입력 마지막을 보면 0 0 을 입력하면 종료가 된다. 따라서 while문 전체로 수행하고 n이 0, m이 0을 입력 받을 때 종료시켜야 한다.

2. 상근 = {1,2,3} 선영 = {1,2,4} 오름 차순으로 정렬 되어있기 때문에 이분 탐색 알고리즘이 적합하다.

3. 상근의 인덱스를 i로, 선영을 j로 잡고 값들이 작으면 인덱스 ++

4. 상근의 값이 크면 선영이 인덱스를 ++

5. 선영의 값이 크면 상근의 인덱스를 ++

 

3. 코드

 

package week09;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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

        while(true) {
            StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

            int N = Integer.parseInt(stringTokenizer.nextToken());
            int M = Integer.parseInt(stringTokenizer.nextToken());

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

            int[] one = new int[N];
            int[] two = new int[M];
            int count = 0;

            for (int i = 0; i < N; i++) {
                one[i] = Integer.parseInt(bufferedReader.readLine());
            }

            for (int i = 0; i < M; i++) {
                two[i] = Integer.parseInt(bufferedReader.readLine());
            }

            int i = 0;
            int j = 0;

            while(i!=N && j!=M){
                if(one[i] == two[j]){
                    count++;
                    i++;
                    j++;
                }else if(one[i] > two[j]){
                    j++;
                }else{
                    i++;
                }
            }

            System.out.println(count);
        }

    }
}