[Gold IV] 비슷한 단어 - 2179 (Java)

문제 요약

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

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

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

---

문제 분석

각 단어별로 모든 접두사를 구한 후 맵에 넣어준다. 그 후 최장길이를 가지는 접두사를 구한 뒤, 그 접두사를 키로하는 리스트의 0,1번째 값을 출력하면 끝!

 

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());
        String[] words = new String[N];
        LinkedHashMap<String, ArrayList<Integer>> prefixMap = new LinkedHashMap<>();

        //  단어의 모든 접두사를 구하고, 각 접두사와 그 접두사를 가진 단어들을 prefixMap에 저장
        /*
            예를들어 'abc', 'abd'가 입력됐다고 한다면
            a접두사에 0추가
            ab접두사에 0추가
            abc접두사에 0추가
            --------------
            a접두사에 1추가
            ab접두사에 1추가
            abd접두사에 1추가
         */
        for (int i = 0; i < N; i++) {
            words[i] = br.readLine();
            StringBuilder prefix = new StringBuilder();
            for (char ch : words[i].toCharArray()) {
                prefix.append(ch);
                if(prefixMap.containsKey(prefix.toString()) == false){
                    prefixMap.put(prefix.toString(), new ArrayList<>());
                }
                prefixMap.get(prefix.toString()).add(i);
            }
        }
        // 접두사 순차탐색
        // 접두사의 최고길이
        int maxLength = -1;
        // 최고길이를 가지는 접두사
        String maxPrefix = "";
        // prefixMap의 모든 접두사들을 순차탐색
        for(String prefix : prefixMap.keySet()){
            // 해당 접두사를 가지는 word들의 인덱스를 가지고 있는 리스트 가져오기
            ArrayList<Integer> list = prefixMap.get(prefix);
            // 해당 접두사를 가지는 word가 2개 이상이고, maxLength보다 긴 접두사라면 갱신.
            if(list.size() >= 2 && prefix.length() > maxLength){
                maxLength = prefix.length();
                maxPrefix = prefix;
            }
        }

        if(maxLength == -1){
            System.out.println(words[0]);
            System.out.println(words[1]);
        }
        else{
            // 위에서 찾은 가장 긴 접두사를 가지는 word 인덱스 리스트 가져오기
            ArrayList<Integer> list = prefixMap.get(maxPrefix);
            // 앞에서부터 2개 출력.
            System.out.println(words[list.get(0)]);
            System.out.println(words[list.get(1)]);
        }

    }
}

---

정리

새로 배운 내용

HashMap과 LinkedHashMap은 다르다.

개선할 점

다른 로직으로 푸는 법을 고민중이다. 

더 찾아볼만한 사항

없

---