99클럽 코테 스터디 2일차 TIL - 문자열, 해시

항해99 코테 스터디 2일차 문제인 백준의 '비슷한 단어'는 가장 비슷한 단어 두개를 찾는 문제다. 난이도는 골드4이며 Map과 문자열 정렬을 통해 해결할 수 있다.

 

오늘의 문제 - 백준 2179번 비슷한 단어 문제 정보

문제 키워드

- 문자열, 해시, 정렬

난이도

- 골드4

 

문제 요약

• N개의 영단어 중 가장 비슷한 두 단어를 찾아 출력하는 문제이다.
• 여기서 "비슷한"의 정도는, prefix가 같은 부분의 길이를 의미한다.
  • ex) ab & abc → 2, ab & cd → 0
• 가장 비슷한 단어가 여러 쌍인 경우, 문자의 등장 순서를 기준으로 정답을 골라야 한다.
  • 답이 될 수 있는 단어 S, T가 있을 때, S의 순서가 가장 빠른 경우를 선택한다.
  • S가 동일한 케이스가 여러개라면, T의 순서가 더 빠른 경우를 선택한다.
• 같은 단어는 비슷하다고 보지 않는다.

 

문제 풀이 과정  

• N이 최대 2만개이기 때문에 모든 단어를 브루트 포스로 비교하는 것은 불가능하다.
• 사전순으로 정렬 후 인접한 단어들끼리만 확인해도 가장 비슷한 단어를 구할 수 있다.
  • 단, 같은 단어는 어차피 무시되므로 인덱스가 더 빠른 하나만 고려한다.
  • 후에 단어의 인덱스를 비교해야 하므로 단어 자체와 인덱스를 보관하는 Word 클래스를 만든다.
• 가장 비슷한 단어가 여러 쌍인 경우를 고려하기 위해 정답 그룹을 저장해야 한다.
  • 예를 들어 ab, abc, abds가 있다면 이 중에서 인덱스가 빠른 두개를 선택해야 한다.
• 비슷한 정도가 같은 단어쌍이 여러개인 경우를 고려하기 위해, 정답 후보 리스트를 저장해야 한다.
  • 예를 들어 (ab, abc, abds)와 (acd, acb, ack)가 있다면 더 작은 인덱스를 가진 그룹이 정답 그룹이 된다.

코드

import java.util.*;
import java.io.*;
import java.util.stream.Collectors;

class P2179 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        // 단어 배열 입력 받기 (중복된 단어는 한번만 받기)
        Map<String, Word> wordMap = new HashMap<>();
        for (int i = 0; i < N; i++) {
            String word = br.readLine();
            wordMap.putIfAbsent(word, new Word(i, word));
        }

        // 단어 배열 사전순으로 정렬하기
        List<Word> words = wordMap.keySet().stream()
                .sorted()
                .map(wordMap::get)
                .collect(Collectors.toList());

        // 정렬 후 인접한 단어들끼리 얼마나 비슷한지 확인
        // 전체에서 가장 비슷한 단어들을 저장
        String maxPrefix = null;
        List<Word> maxPrefixGroup = new ArrayList<>();
        List<List<Word>> answerCandidates = new ArrayList<>();

        for (int i = 0; i < words.size()-1; i++) {
            // 인접한 두 단어의 접두사를 구함
            Word word1 = words.get(i);
            Word word2 = words.get(i + 1);
            String prefix = getPrefix(word1.word, word2.word);

            // 1. 맨 처음에는 무조건 갱신
            if (maxPrefix == null) {
                maxPrefix = prefix;
                maxPrefixGroup.add(word1);
                maxPrefixGroup.add(word2);
            }
            // 2. 현재 가장 긴 접두사와 이번 접두사가 같은 경우
            // 새로운 단어를 정답 그룹에 추가
            else if (prefix.equals(maxPrefix)) {
                maxPrefixGroup.add(word2);
            }
            // 3. 현재 가장 긴 접두사보다 이번 접두사가 더 긴 경우
            // 가장 긴 접두사 및 정답 그룹 업데이트
            // + 현재까지의 정답 후보 그룹 초기화
            else if (prefix.length() > maxPrefix.length()) {
                answerCandidates.clear();
                maxPrefix = prefix;
                maxPrefixGroup.clear();
                maxPrefixGroup.add(word1);
                maxPrefixGroup.add(word2);
            }
            // 4. 현재 가장 긴 접두사와 이번 접두사의 길이가 같은 경우
            // 이전까지의 정답 그룹과 새로운 정답 그룹의 인덱스를 비교해야 함
            // 정답 후보 그룹에 지금까지의 정답 그룹을 넣고, 새로운 정답 그룹을 계속해서 구함
            else if (prefix.length() == maxPrefix.length()) {
                answerCandidates.add(new ArrayList<>(maxPrefixGroup));
                maxPrefix = prefix;
                maxPrefixGroup.clear();
                maxPrefixGroup.add(word1);
                maxPrefixGroup.add(word2);
            }
        }
        // 모든 단어 확인이 끝나면, 현재 정답 그룹을 후보 리스트에 추가
        answerCandidates.add(new ArrayList<>(maxPrefixGroup));

        // 정답 후보 리스트 중 가장 빠르게 등장한 단어가 있는 그룹이 정답임
        int minIdx = Integer.MAX_VALUE;
        for (List<Word> candidates : answerCandidates) {
            candidates.sort(Comparator.comparingInt(o -> o.no));
            if (candidates.get(0).no < minIdx) {
                minIdx = candidates.get(0).no;
                maxPrefixGroup = candidates;
            }
        }

        // 정답 중에서 등장 순으로 빠른 2개만 출력
        for (Word s : maxPrefixGroup.subList(0, 2)) {
            System.out.println(s.word);
        }
    }

    private static String getPrefix(String w1, String w2) {
        int minLen = Integer.min(w1.length(), w2.length());
        for (int i = 0; i < minLen; i++) {
            if (w1.charAt(i) != w2.charAt(i)) {
                return w1.substring(0, i);
            }
        }
        return w1.substring(0, minLen);
    }

    public static class Word {
        int no;
        String word;

        public Word(int no, String word) {
            this.no = no;
            this.word = word;
        }
    }
}

• 시간복잡도: O(NlogN) → 정렬
• 공간복잡도: O(N)

 

오늘의 학습 회고

새롭게 알게된 것

• 리스트를 정렬하는 다양한 방법을 알게 되었다.
  • list.stream().sorted()
  • list.sort(Comparator.comparingInt(o -> o.no))    // Int 비교로 정렬
  • Arrays.sort(arr, new Comparator<> { ... })
• 반례를 꼼꼼히 생각하자.
  • 이번 문제에서는 정답 후보가 여러개인 경우 S와 T의 등장 순서가 빠른게 정답이었는데, 이에 대한 모든 케이스를 고려해서 문제를 풀어야 했다.
  • 예를 들어 acd, ab, abc, ace 순서로 등장하는 경우 정답이 ab&abc가 아니라 acd&ace가 되어야 하는 케이스를 놓쳐서 문제를 틀렸었다.
  • 정렬한 뒤에 순서가 ab, abc, acd, ace가 되기 때문에 ab&abc가 먼저 발견되고, 이후 등장한 acd&ace는 앞선 케이스보다 비슷한 정도가 크지 않기 때문에 정답이 갱신되지 않았다. 이 경우도 처리하기 위해 코드에 정답 후보 그룹을 추가하여 해결하였다.