백준 2179번 : 비슷한 단어 [자바]

 

 

🧫 문제 분석

 

✔️ 출처

비슷한 단 골드 4

 

📖 문제

 

 

문자열 정렬 문제다. 

급한 마음으로 하니 안풀리다가 생각을 정리하고 설계한다음 풀어보니 바로 풀렸다.

O(n^2)으로 풀 수 없을 것 같아서 

입력받은 단어들을 저장한 배열과 사전순으로 정렬한 리스트를 만들고, TreeSet으로 풀었다.

 

주어진 단어들의 접두사 (단어 앞부분 공통적으로 나타나는 부분문자열)가 최대가되는 두쌍을 찾아야한다. 

 

문제는 접두사 길이가 최대인 경우가 여러개일때 앞 인덱스에 있는 쌍을 출력해야한다는 것이다. 

따라서 사전순으로 정렬한 리스트를 돌면서 i, i+1 번째 단어의 접두사 길이를 탐색하고, 

접두사의 길이가 max 보다 길다면 이전의 max길이였던 단어들을 모두 제거하기 위해 TreeSet을 초기화하고

새롭게 갱신하게 해준 두 단어를 TreeSet에 저장한다. 

 

만약 max와 i, i+1 단어의 접두사 길이가 같다면

i, i+1 단어를 원래 인덱스와 함께 TreeSet에 저장한다. 

 

이유는 문제에서 길이가 최대인 단어가 여러개라면 앞 인덱스를 출력하라 되어있고,

현재 리스트는 정렬되었으므로 원래 인덱스가 아니다. 따라서 TreeSet에 저장함으로써 

길이가 max이면서 앞인덱스인 것을 빠르게 찾기 위해 저장한다. 

 

현재 TreeSet에는 Max 길이인 단어들의 인덱스가 오름차순으로 정렬되어있다.

 

정렬 리스트의 탐색이 끝나면

ts.pollFirst()로 길이가 max인 가장 앞인덱스 단어를 꺼낸다. 이 단어가 S가 된다. 

그리고 prefix를 얻고 ts.pollFirst()로 TreeSet에 저장된 모든 단어들을 꺼내서 

startWith()으로 접두사가 같은지 확인한다. 

같은 것을 찾으면 그 단어가 T가 된다. 

 

 

 

사전순으로 정렬하면 비슷한 단어끼리 묶여진다. 

a

aa

aaab

aaaab

 

abc

abcd

abchldp

abe

 

따라서 i번째와 i+1번째의 접두사 길이를 탐색하면 된다.

 

 

---

🔅 문제 풀이

import java.io.*;
import java.util.*;

public class Main {

    static class Word {
        String name; // 단어 이름
        int idx; // 단어의 원래 인덱스

        public Word(String name, int idx) {
            this.name = name;
            this.idx = idx;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());

        String[] words = new String[n];
        List<Word> list = new ArrayList<>(); // 정렬된 영단어 리스트

        for (int i = 0; i < n; i++) {
            words[i] = br.readLine();
            list.add(new Word(words[i], i));
        }

        // 사전순 정렬
        Collections.sort(list, (o1, o2) -> o1.name.compareTo(o2.name));

        // 접두사 길이에 따른 단어들의 인덱스 저장
        TreeSet<Integer> ts = new TreeSet<>();
        int max = 0;

        // 접두사 탐색
        for (int i = 0; i < n - 1; i++) {
            String word1 = list.get(i).name;
            String word2 = list.get(i + 1).name;
            int len = Math.min(word1.length(), word2.length()); // 짧은 단어 기준으로 순회
            int cnt = 0; // 접두사 길이 측정
            
            if (len < max) continue; // max접두사길이보다 단어의 탐색길이가 더 작다면 다음으로 넘어간다.

            for (int j = 0; j < len; j++) {
                if (word1.charAt(j) == word2.charAt(j)) {
                    cnt++;
                } else {
                    break;
                }
            }

            // 접두사 길이가 max보다 크다면 갱신
            if (cnt > max) {
                ts.clear(); // 짧은건 필요없어졌으므로 초기화

                ts.add(list.get(i).idx);
                ts.add(list.get(i + 1).idx);
                max = cnt;

            } else if (cnt == max) { // 길이가 같을때 앞쪽 있는 단어인지를 위해 우선 저장
                ts.add(list.get(i).idx);
                ts.add(list.get(i + 1).idx);
            }
        }

        // 비어있다면 맨 앞 2개를 출력 (접두사 길이가 0이라는 의미이므로)
        if (ts.isEmpty()) {
            sb.append(words[0]).append("\n").append(words[1]);
            System.out.println(sb.toString());
            return;
        }

        int S = ts.pollFirst(); // 맨 처음것이 max길이이면서 가장 앞에있는 S임
        String prefix = words[S].substring(0, max); // 접두사를 추출

        while (!ts.isEmpty()) { // max길이인 단어들을 순서대로뽑아내서 접두사가 같은 것을 탐색
            int idx = ts.pollFirst();
            if (words[idx].startsWith(prefix)) {
                sb.append(words[S]).append("\n").append(words[idx]);
                break;
            }
        }
        
        System.out.println(sb.toString());
    }
}

 

 

 

❗ 오답노트 / 필요한 지식

1.  천천히 생각하면서 풀어야 잘 풀린다.