👀 문제 분석
입력된 N개의 영단어 중 가장 비슷한 두 단어를 구한다.
두 단어의 비슷한 정도는 두 단어의 접두사 길이로 측정한다.
접두사 길이가 최대인 경우가 여러 개일 경우 입력되는 순서대로 제일 앞쪽에 있는 단어를 답으로 한다.
즉, 답으로 S라는 문자열과 T라는 문자열을 출력한다고 했을 때, 우선 S가 입력되는 순서대로 제일 앞쪽에 있는 단어인 경우를 출력하고, 그런 경우도 여러 개 있을 때에는 그 중에서 T가 입력되는 순서대로 제일 앞쪽에 있는 단어인 경우를 출력한다.
⚒️ 설계
-
단어의 수 N과 N만큼의 단어들을 입력받는다.
-
입력된 단어를 배열에 저장한다.
-
단어 리스트에서 인접한 두 단어를 비교하고 접두사의 길이를 계산한다.
-
최대 접두사의 길이를 갱신한다.
-
최대 접두사의 길이를 가진 단어 두 개를 조건에 따라 가장 먼저 입력된 순서를 가진 단어를 출력한다.
📝 코드
import java.io.*;
import java.util.*;
public class Main {
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 = readWords(br, n);
List<Word> result = findSimilarWords(words);
printResult(result);
br.close();
}
private static List<Word> readWords(BufferedReader br, int n) throws IOException {
List<Word> words = new ArrayList<>();
for (int i = 0; i < n; i++) {
words.add(new Word(i, br.readLine()));
}
return words;
}
private static List<Word> findSimilarWords(List<Word> words) {
int maxPrefixLength = 0;
Word first = new Word(Integer.MAX_VALUE, "");
Word second = new Word(Integer.MAX_VALUE, "");
for (int i = 0; i < words.size(); i++) {
for (int j = i + 1; j < words.size(); j++) {
Word w1 = words.get(i);
Word w2 = words.get(j);
int prefixLength = getPrefixLength(w1.value, w2.value);
if (prefixLength > maxPrefixLength) {
maxPrefixLength = prefixLength;
first = w1;
second = w2;
}
if (prefixLength == maxPrefixLength) {
if (w1.index < first.index ||
(w1.index == first.index && w2.index < second.index)) {
first = w1;
second = w2;
}
}
}
}
return Arrays.asList(first, second);
}
private static int getPrefixLength(String s1, String s2) {
int length = 0;
while (length < s1.length() && length < s2.length() && s1.charAt(length) == s2.charAt(length)) {
length++;
}
return length;
}
private static void printResult(List<Word> result) {
System.out.println(result.get(0).value);
System.out.println(result.get(1).value);
}
static class Word {
int index;
String value;
Word(int index, String value) {
this.index = index;
this.value = value;
}
}
}
⌛️ 시간복잡도
단어의 평균 길이를 m이라고 정의한 후, 모든 단어 쌍을 비교하면 아래와 같은 시간 복잡도를 가진다.
하지만 길이가 100자 이하로 제한되어 있기때문에 m은 생략해도 된다.
👩🏻💻 느낀점
최대 접두사의 길이를 가진 단어가 두 개일 경우에 먼저 입력된 단어가 출력되어야 한다는 조건을 까먹고 처음에 정렬을 한 후에 인접한 단어들을 비교하는 설계를 해서 출력값이 올바르지 않게 나왔다.
그래서 기존 정렬하는 부분을 제거하고 이중 for문을 이용하여 모든 쌍을 순회하는 설계로 변경하여 풀이하였다.
문제를 꼼꼼하게 읽고 조건을 놓치지 않게 조심해야겠다.
순서를 보장하기 위해서 index와 value를 다루는 Word 객체를 생성해서 사용하였는데 코드의 길이가 길어지긴 했지만 가독성은 조금 더 높아지는 것 같다.
하지만, 실제 코딩 테스트에서는 메서드를 분리하는 것에 시간을 많이 들이는 것은 비효율적일 것이라는 생각이 들었다. 상황에 따른 빠른 판단이 필요할 것 같다.
✔️ 소요 시간 : 40분
