백준 2179번 <비슷한 단어>

백준 알고리즘 2179번

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

2179번: 비슷한 단어

---

2179번

N개의 영단어들이 주어졌을 때, 가장 비슷한 두 단어를 구해내는 프로그램을 작성하시오.

두 단어의 비슷한 정도는 두 단어의 접두사의 길이로 측정한다. 접두사란 두 단어의 앞부분에서 공통적으로 나타나는 부분문자열을 말한다. 즉, 두 단어의 앞에서부터 M개의 글자들이 같으면서 M이 최대인 경우를 구하는 것이다. "AHEHHEH", "AHAHEH"의 접두사는 "AH"가 되고, "AB", "CD"의 접두사는 ""(길이가 0)이 된다.

접두사의 길이가 최대인 경우가 여러 개일 때에는 입력되는 순서대로 제일 앞쪽에 있는 단어를 답으로 한다. 즉, 답으로 S라는 문자열과 T라는 문자열을 출력한다고 했을 때, 우선 S가 입력되는 순서대로 제일 앞쪽에 있는 단어인 경우를 출력하고, 그런 경우도 여러 개 있을 때에는 그 중에서 T가 입력되는 순서대로 제일 앞쪽에 있는 단어인 경우를 출력한다.

---

문제 해결

그냥 하나하나 비교했다!

 

N은 최대 2만개이고 각각 하나씩 비교한다고 하면 N(N+1) / 2 만큼의 연산을 해야 되서 최대 2억번이지만 가지치기를 잘하면 가능할 것 같았다.

 

하나씩 비교하면서 일단 첫 글자가 서로 다르면 보지 않았다.

그리고서 check 메소드를 호출해서 두 개의 가장 긴 접두사를 구했다,

check에서는 2개의 문자열 중 길이가 짧은 문자열을 기준으로 for문을 돌려서 가장 긴 접두사를 구했다. 

for문을 돌리기 전에 길이가 짧은 문자열의 길이가 현재 구해 둔 가장 긴 접두사보다 짧다면 이미 구해놓은 것이 더 길기 때문에 -1을 반환했다.

for문에서는 서로 같지 않은 경우에는 접두사를 모두 구한 것이기 때문에 for문의 변수를 반환해주었다.

 

---

코드

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

public class BOJ_2179 {
    static int ans;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String[] strs = new String[N];
        for (int i = 0; i < N; i++) {
            strs[i] = br.readLine();
        }
        ans = Integer.MIN_VALUE;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N-1; i++) {
            for (int j = i + 1; j < N; j++) {
                if (strs[i].charAt(0) != strs[j].charAt(0)) continue;
                int chk = check(strs[i], strs[j]);
                if (ans < chk) {
                    ans = chk;
                    sb.setLength(0);
                    sb.append(strs[i]).append("\n").append(strs[j]);
                }
            }
        }
        System.out.println(sb);
    }

    static int check(String a, String b) {
        int M = Math.min(a.length(), b.length());
        if (ans > M) return -1;
        for (int i = 0; i < M; i++) {
            if (a.charAt(i) != b.charAt(i)) {
                return i;
            }
        }
        return M;
    }
}

---

결과

 

---