백준 - 2179번 : 비슷한 단어 Java

문제

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

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

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

---

입력

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

출력

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

---

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        List<String> arr = new ArrayList<>();
        
        for(int i=0; i<n; i++){
            String str = sc.next();
            if(!arr.contains(str)) arr.add(str);
        }
        
        int s = 0;
        int t = 0;
        int max = 0;
        
        for(int i=0; i<n-1; i++){
            String str1 = arr.get(i);
            for(int j=i+1; j<n; j++){
                int cnt = 0;
                String str2 = arr.get(j);
                for(int k=0; k<Math.min(str1.length(), str2.length()); k++){
                    if(str1.charAt(k) == str2.charAt(k)) cnt++;
                    else break;
                }
                if(cnt > max){
                    s = i;
                    t = j;
                    max = cnt;
                }
            }
        }
        System.out.println(arr.get(s));
        System.out.println(arr.get(t));
    }
}

 

문제 설명이 길고 조건이 많아서 어려워 보이지만 정리하면 두 문자열을 비교해서 같은 문자를 가진 수가 가장 큰 두 문자열을 찾으면 된다.

→ charAt으로 두 문자열을 비교하여 공통으로 가진 문자의 개수를 cnt에, 두 문자열의 인덱스를 각각 s와 t에 저장 후 다른 경우의 조합과 비교하여 최대 cnt를 찾으면 된다.

 

처음에 배열로 n개의 문자열을 받았다가 틀렸는데 이유는 출력 조건의 "같은 단어는 제외"를 지키지 않았기 때문... 리스트로 받아서 중복 제거를 해줬다.

출력 순서는 두 단어 중 먼저 입력된 단어 먼저 출력 해줘야 하고, 주어진 단어들 안에서 두 가지 씩 조합의 경우의 수를 구하는 것이므로 위와 같이 2중 for문을 돌게한다.

 

또 한번 틀렸던 이유는 charAt으로 두 문자열을 비교하는 반복문에서 반복문의 크기를 Math.min( )으로 계산하지 않았기 때문이다...

아무 생각 없이 첫번째 문자열인 str1.length( )로 했다가 틀린걸 보면 아마 index out of bound 에러가 난 것 같다.

str1의 크기가 str2 보다 클 때 str1의 크기로 반복문을 돌게되면 str2에는 존재하지 않는 인덱스를 찾게 되기 때문.

 

 

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