14426 접두사 찾기

 

 

 

입력 예시

 

5 10
baekjoononlinejudge
startlink
codeplus
sundaycoding
codingsh
baekjoon
star
start
code
sunday
coding
cod
online
judge
plus

 

입력으로 주어진 N개의 문자열을 오름차순 정렬한 뒤,

-> baekjoononlinejudge, codeplus, codingsh, startlink, sundaycoding

 

이분탐색으로 M개의 문자열이 접두사인지 여부를 파악하면 된다.

 

 

 

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



public class Main {
	
	
	static String [] input;
	static int N;
	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(), " ");
       	   N = Integer.parseInt(st.nextToken());
       	   int M = Integer.parseInt(st.nextToken());
       	   input = new String[N];
       	   
       	   
       	   for(int i=0; i<N; i++) {
       		st = new StringTokenizer(br.readLine(), " ");
       		input[i]= st.nextToken();
       	   }
       	   
       	   Arrays.sort(input);
       	   
       	   while(M-->0) {
       		   
       		st = new StringTokenizer(br.readLine(), " ");
       		String word = st.nextToken();
       		
       		solve(word);   		   
       		   
       		   
       	   }
       	   
       	   System.out.println(count);
       	   
       	   
       	   }
    
    
    public static void solve(String word) {
    	
    	
    	int left = 0;
    	int right = N-1;
    	
    	while(left<=right) {    		
    		
    		int mid = (left + right)/2;
    	
    		
    		if(input[mid].substring(0,word.length()).equals(word)) {
    			count++;
    			break;
    			
    		}else {
    			
    			
    			if(input[mid].compareTo(word)>=0) {
    		
    				right = mid-1;
    			}else {
    				
    				left = mid + 1;
    			}
    			
    		} 		
    		
    	}   	
    }
}

 

 

참고 블로그 : https://upcurvewave.tistory.com/460

백준 14425 문자열 집합 (이분 탐색을 이용한 JAVA 자바 풀이)