[Gold IV][JAVA]백준 2179번:비슷한 단어

문제 바로가기 > [Gold IV]백준 2179번:비슷한 단어

분류

• 자료 구조
• 문자열
• 정렬
• 해시를 사용한 집합과 맵

풀이

문제에서 요구하는 것은 주어진 문자열 중에서 가장 비슷한 두 단어를 찾는 것입니다. 단, 순서대로 제일 앞쪽에 있는 단어인 경우를 출력해야합니다.

1. 문자열을 중복 없이 입력 받기 위해 ArrayList를 사용하여 중복을 제거합니다.
2. 중복을 제거한 문자열 리스트에서 이중 반복문을 통해 각 문자열들을 비교합니다.
3. 비교하는 두 문자열의 접두사의 길이를 비교하여 최대인 경우를 찾을 때마다 갱신합니다.

ArrayList를 사용한 이유?

여러 문자열을 입력 받아야 하고, 입력된 문자열들 간에 중복이 있을 수 있기 때문에 중복을 허용하지 않고 문자열을 저장합니다. 이렇게 하면 후에 중복된 문자열을 추가하지 않으면서도 입력된 순서대로 문자열을 유지할 수 있습니다.

[Java] List에 특정 값이 포함되어 있는지 확인하기

Java - ArrayList.contains()

[Java 기초] ArrayList를 다루는 함수들(add, set, get, remove, size)

정답

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


public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        List<String> word = new ArrayList<>();
        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            if (!word.contains(str))
                word.add(str);
        }

        int max = Integer.MIN_VALUE;
        int wordA = 0, wordB = 0;
        for (int i = 0; i < word.size() - 1; i++) {
            String str1 = word.get(i);
            for (int j = i + 1; j < word.size(); j++) {
                int count = 0;
                String str2 = word.get(j);

                int len = Math.min(str1.length(), str2.length());
                for (int l = 0; l < len; l++) {
                    if (str1.charAt(l) != str2.charAt(l))
                        break;
                    count++;
                }

                if (max < count) {
                    max = count;
                    wordA = i;
                    wordB = j;
                }
            }
        }

        System.out.println(word.get(wordA));
        System.out.println(word.get(wordB));
    }
}