[Problem Solving] BOJ 14426: 접두사 찾기

문제 링크: https://www.acmicpc.net/problem/14426

 

S를 정렬한다.

S에서 각 T[i]에 대해 이진탐색 한다.

java에서 이진탐색의 결과는 정확히 일치하는 값이 있으면 그 값이 존재하는 S에서의 index를 반환하고, 일치하지 값이 없으면 T[i]가 삽입될 자리를 -index-1로 반환한다. 이 때 index = -index-1로 바꿔주면 S[index]는 T[i]를 접두사로 갖는 문자열이다.

index가 N보다 작고 S[index]가 T[i]로 시작하는 문자열인지 startsWith함수를 사용해 확인하여 이 결과가 참이라면 result를 1증가시킨다.

 

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

public class Main 
{
    public static int N, M;
    public static String[] S;
    public static String[] T;
    public static int result = 0;

    public static void input(BufferedReader br) throws IOException
    {
        String[] line = br.readLine().split(" ");
        N = Integer.parseInt(line[0]);
        M = Integer.parseInt(line[1]);
        S = new String[N];
        T = new String[M];
        for(int i = 0; i < N; i++)
        {
            S[i] = br.readLine();
        }
        for(int i = 0; i < M; i++)
        {
            T[i] = br.readLine();
        }
    }

    public static void solution()
    {
        Arrays.sort(S);
        for(int i = 0; i < M; i++)
        {
            int index = Arrays.binarySearch(S, T[i]);
            if(index < 0)
            {
                index = -index - 1;
            }
            if(index < N && S[index].startsWith(T[i]))
            {
                ++result;
            }
        }
    }

    public static void output()
    {
        System.out.println(result);
    }

    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // Scanner sc = new Scanner(System.in);
        input(br);
        // input(sc);
        solution();
        output();
    }
}