[java][백준] 2179 - 비슷한 단어

문제

풀이

문제 해석

1. N개의 영단어가 주어질 때, 가장 비슷한 단어를 구해야 한다.

2. 비슷한 정도는 접두사의 길이, 즉 앞단어가 얼마나 비슷한지가 쟁점이다.

3. 접두사의 길이가 최대인 경우가 여러 개 일 경우에는 앞쪽에 있는 단어를 출력한다.

문제 풀이

1. 공통부분문자열(Longest Common Substring)이지만 접두사만 보고 있기 때문에 알고리즘을 사용할 필요 없다.

2. 시간제한이 2초이고 n이 20,000개 이기 때문에 단순 비교로도 구현 가능하다.

3. 최대겹치는 부분의 길이보다 작은 문자열이라면 비교조차 할 필요 없다.

소스코드

package online.judge.baekjoon;

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

/**
 * 비슷한 단어
 * 골드 4
 *
 */
public class No2179 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        String[] strArr = new String[n];
        for (int i = 0; i < n; i++) {
            strArr[i] = br.readLine();
        }

        int a = 0, b = 0, max = 0;
        for (int i = 0; i < n - 1; i++) {
            //max값보다 짧은 문자열이라면 비교 할 필요 없음
            if(max >= strArr[i].length()) continue;
            for (int j = i+1; j < n; j++) {
                //max값보다 짧은 문자열이라면 비교 할 필요 없음
                if(max >= strArr[j].length()) continue;
                int cnt = 0;
                int repeat = Math.min(strArr[i].length(), strArr[j].length());
                for (int k = 0; k < repeat; k++) {
                    if(strArr[i].charAt(k) == strArr[j].charAt(k)) cnt++;
                    else break;
                }

                if(cnt > max){
                    max = cnt;
                    a = i;
                    b = j;
                }
            }
        }

        System.out.println(strArr[a]);
        System.out.print(strArr[b]);
    }
}

마무리

1. max값보다 작은 문자열은 무시하는 부분을 통해 꽤 큰 시간을 줄일 수 있었다.

2. 하지만 문자열이 길이순으로 입력되었다면 상관없는 부분이긴 하다.