99클럽 코테 스터디 2일차 TIL: [백준] 2179. 비슷한 단어

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

 

반복문을 통해 단순히 구현하면 되는 문제이다. 단순한 문제 같지만 헤맸다. 

• substring()을 통해 두 문자열을 비교하면 메모리 초과가 난다. 따라서 charAt으로 각 자리를 비교하면 된다. 그리고 비교 결과 다르면 반복문을 빠져나오면 된다.
• 접두사 길이가 가장 긴 두 개 이상의 문자열을 set이나 list에 저장하려고 했으나, 굳이 할 필요 없다. 어차피 문자열들 중 가장 먼저 입력된 문자열 2개를 출력해야 하는데, sameCount와 sameCountMax가 같은 경우에 값을 갱신하지 않고 sameCount > sameCountMax인 경우에만 값을 갱신하면 자연스럽게 가장 먼저 입력된 문자열 2개만 출력할 수 있다.

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int n;
    static List<String> list = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            list.add(br.readLine());
        }

        int sameCountMax = 0;
        int idx1 = -1;
        int idx2 = -1;

        // 두 단어씩 비교
        for (int i = 0; i < n - 1; i++) {
            String str1 = list.get(i);
            for (int j = i + 1; j < n; j++) {
                String str2 = list.get(j);
                int len = Math.min(str1.length(), str2.length());
                int sameCount = 0;
                for (int k = 0; k < len; k++) {
                    if (str1.charAt(k) != str2.charAt(k)) {
                        break;
                    }
                    sameCount++;
                }
                if (sameCount > sameCountMax) {
                    sameCountMax = sameCount;
                    idx1 = i;
                    idx2 = j;
                }
            }
        }

        System.out.println(list.get(idx1));
        System.out.println(list.get(idx2));
    }
}