BOJ 2179 비슷한 단어

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

문제

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

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

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

---

입력

첫째 줄에 N(2 ≤ N ≤ 20,000)이 주어진다. 다음 N개의 줄에 알파벳 소문자로만 이루어진 길이 100자 이하의 서로 다른 영단어가 주어진다.

---

출력

첫째 줄에 S를, 둘째 줄에 T를 출력한다. 단, 이 두 단어는 서로 달라야 한다. 즉, 가장 비슷한 두 단어를 구할 때 같은 단어는 제외하는 것이다.

---

예제 입력 1

9
noon
is
lunch
for
most
noone
waits
until
two

예제 출력 1

noon
noone

예제 입력 2

4
abcd
abe
abc
abchldp

예제 출력 2

abcd
abc

---

코드

문제를 처음 읽었을 때, 답의 출력 방식에 대한 설명을 이해하지 못해 몇 번은 읽은 것 같다.

간단하게 말하면, 최고 길이의 접두사를 가지는 단어 쌍이 여러 개 있을 때, 가장 먼저 입력받은 단어들을 가지고 있는 단어 쌍을 출력하면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Main {

    static class Word{
        String word;
        int index; // 단어를 입력받은 순서

        public Word(String word, int index) {
            this.word = word;
            this.index = index;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        List<Word> words = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            words.add(new Word(br.readLine(), i));
        }

        // 단어를 기준으로 정렬한다.
        words.sort(Comparator.comparing(w -> w.word));

        // 가장 긴 접두사의 길이
        int maxPrefixLength = -1;
        // 정답이 될 수 있는 단어 쌍을 저장하기 위한 List
        List<Word[]> nominees = null;

        for (int i = 0; i < words.size(); i++) {
            Word check = words.get(i);

            // 정답이 될 수 있는 단어 쌍을 만들기 위해 검사 중인 단어와 쌍을 이룰 수 있는 단어 탐색
            for (int j = i + 1; j < words.size(); j++) {
                Word target = words.get(j);

                // check와 target의 접두사 길이를 계산
                int checkIdx = 0;
                for (; checkIdx < check.word.length() && check.word.charAt(checkIdx) == target.word.charAt(checkIdx); checkIdx++) ;

                // check와 target이 서로 같은 단어인 경우 탐색 중지
                if(check.word.length() == checkIdx && target.word.length() == checkIdx) {
                    break;
                }

                // 계산된 접두사의 길이가 이전 최대 접두사의 길이보다 긴 경우, 정답 후보 쌍 List 초기화
                if(checkIdx > maxPrefixLength) {
                    maxPrefixLength = checkIdx;
                    nominees = new ArrayList<>();
                }

                // 최대 접두사의 길이와 계산된 접두사의 길이가 같을 경우, 정답 후보에 check, target 쌍 추가
                if(checkIdx == maxPrefixLength) {
                    if(check.index < target.index) {
                        nominees.add(new Word[] {check, target});
                    } else {
                        nominees.add(new Word[] {target, check});
                    }
                } else {
                    break;
                }
            }
        }

        // 정답 후보 중 가장 먼저 입력받은 쌍을 정답으로 출력
        int answerIdx = 0;
        for (int i = 1; i < nominees.size(); i++) {
            if(nominees.get(i)[0].index < nominees.get(answerIdx)[0].index) {
                answerIdx = i;
            } else if(nominees.get(i)[0].index == nominees.get(answerIdx)[0].index) {
                if(nominees.get(i)[1].index < nominees.get(answerIdx)[1].index) {
                    answerIdx = i;
                }
            }
        }

        StringBuilder answer = new StringBuilder();
        answer.append(nominees.get(answerIdx)[0].word);
        answer.append('\n');
        answer.append(nominees.get(answerIdx)[1].word);

        System.out.println(answer);
    }
}