BOJ14425 문자열 집합

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

14425번: 문자열 집합

SET 자료형을 이용할수도 있지만 이번엔 이분탐색 메소드를 이용해보았다.

 

 

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

public class Main
{
	public static void main(String[] args) throws IOException{
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int count =0;
		
		String[] input1 = br.readLine().split(" ");
		int n= Integer.valueOf(input1[0]);
		int m= Integer.valueOf(input1[1]);
		String[] word1=  new String[n];
		String[] word2=  new String[m];
		for(int i =0; i<n;i++){
		    word1[i]=br.readLine();  
		}
		for(int i =0; i<m;i++){
		    word2[i]=br.readLine();   
		}
		
		Arrays.sort(word1);
		for(int i=0; i<m;i++){
		    if(Arrays.binarySearch(word1,word2[i])>=0) count++;    
		}
		System.out.println(count);
	}
}

 

 

메소드가 아닌 실제 구현 코드

import java.util.Arrays;
import java.util.Scanner;

class Main
{
    static boolean isExist(String[] arr, String x) {
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            int m = (l + r) / 2;
            int compareResult = arr[m].compareTo(x);
            if (compareResult < 0) l = m + 1;
            else if (compareResult > 0) r = m - 1;
            else return true;
        }
        return false;
    }

    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();
        String[] arr = new String[N];
        for (int i = 0; i < N; i++)
            arr[i] = sc.next();

        Arrays.sort(arr);

        int count = 0;
        while (M-- > 0) {
            String x = sc.next();
            if (isExist(arr, x))
                count++;
//            if (Arrays.binarySearch(arr, x) >= 0)
//                count++;
        }
        System.out.println(count);
    }
}