[백준] 2179번 Java (문자열, 정렬)

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

💡문제

풀이

접근법 :

<두 문자열의 공통 길이 구하기>

static int commonLength(String a, String b) {
        int length = Math.min(a.length(), b.length());
        int idx = 0;
        while (idx < length && a.charAt(idx) == b.charAt(idx)) {
            idx++;
        }
        return idx;
    }

• 두 문자열이 주어졌을 때 공통길이를 구하는 메서드이다.
• 공통길이는 첫문자부터 시작하므로 간단하게 idx를 이용해서 구했다.
  
  
  

<단어들을 돌면서 비교하기>

for (int i = 0; i < n - 1; i++) {
            String now = strings[i];
            if(now.length() <= maxLength) continue; // 최대 접두사보다 짧은 문자열은 pass
            for (int j = i+1; j < n; j++) {
                String next = strings[j];
                if(next.length() <= maxLength) continue; // 최대 접두사보다 짧은 문자열은 pass
                int length = commonLength(strings[i], strings[j]);

                if(length > maxLength){
                    maxLength = length;
                    a = strings[i];
                    b = strings[j];
                }
            }
        }

• 이 부분에서 풀이가 아주 오래 걸렸다.
• 처음에는 모든 단어를 돌지 않아도 되는 방법이 있지 않을까? 하는 생각으로 다양한 방법들을 시도해봤다.
• 그렇지만 단어들이 순서 없이 주어지므로 모든 단어를 비교해야만 했다.
• 그냥 이중 for문을 쌩으로 돌리니까 시간이 1420ms가 나와서 중간에 조건을 걸었다.
• 현재 비교하고 있는 단어의 길이가 가장 긴 접두사보다 작거나 같은 경우에는 그냥 지나친다.
• for 문에 조건을 추가하고 나니 엄청나게 시간이 줄어들었다.

내 코드

import java.io.*;

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());
        String[] strings = new String[n];

        for (int i = 0; i < n; i++) {
            strings[i] = br.readLine();
        }

        int maxLength = -1; // 최대길이 접두사
        String a = "";
        String b = "";

        // 출력 시 index값에 따라 나열해야 하므로
        // 이중 for문으로 다음 수와 비교한다.
        for (int i = 0; i < n - 1; i++) {
            String now = strings[i];
            if(now.length() <= maxLength) continue; // 최대 접두사보다 짧은 문자열은 pass
            for (int j = i+1; j < n; j++) {
                String next = strings[j];
                if(next.length() <= maxLength) continue; // 최대 접두사보다 짧은 문자열은 pass
                int length = commonLength(strings[i], strings[j]);

                if(length > maxLength){
                    maxLength = length;
                    a = strings[i];
                    b = strings[j];
                }
            }
        }
        System.out.println(a);
        System.out.println(b);
    }
    
    // 두 문자열의 공통 길이 구하기 (몇번째 단어까지 같은지)
    static int commonLength(String a, String b) {
        int length = Math.min(a.length(), b.length());
        int idx = 0;
        while (idx < length && a.charAt(idx) == b.charAt(idx)) {
            idx++;
        }
        return idx;
    }
}