14425. 문자열 집합 (자바, Java)

앞선 문제와 유사한데, 이번엔 숫자가 아닌 문자열로 바뀌었습니다.

이전에 정렬문제에서, 람다식으로 변환하는 문제를 풀면서 알게된 compareto 매소드 콜을 사용하여 풀었습니다.

그리고 앞 문제의 이진탐색 개념을 콜라보하여서 풀게되었고, 뭔가 개념이 장착된 기분이라 풀고서 아주 기분이 좋았습니다.

 

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

public class Main {

	static int count;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken()); // 집합S에 포함된 문자열들
		int m = Integer.parseInt(st.nextToken()); // 검사해야하는 문자열들
		
		String[] s = new String[n];
		String[] search = new String[m];
		
		for (int i=0; i<n; i++) {
			s[i] = br.readLine();
		}
		
		Arrays.sort(s);
		count = 0; // 집합S에 포함된 갯수
		
		for (int i=0; i<m; i++) {
			search[i] = br.readLine();
			set(s, search[i]);
		}
		
		System.out.println(count);		
		
	}
	
	static void set(String[] s, String search) {
		
		int leftIdx = 0;
		int rightIdx = s.length-1;
		
		while (leftIdx<=rightIdx) {
			int avg = (leftIdx + rightIdx)/2;
			String mid = s[avg]; // 비교대상으로, 범위의 중간부터 비교해준다.
			if (search.compareTo(mid)==0) { 
				// search와 mid가 같을 때
				count++;
				return;
			} else if (search.compareTo(mid)<0) { 
				// search가 mid보다 앞에 올 때
				rightIdx = avg-1;
			} else if (search.compareTo(mid)>0) { 
				// 그냥 else로 표현해도 되지만, 가시성을 위해 표기
				leftIdx = avg+1;
			}			
		}		
		
		return;
	}
}