항해 99 코테스터디 5기 9일차 + [백준] 2179 비슷한 단어 java 풀이

1. 문제 설명 📌

(1) 링크🔗

문제 링크

(2) 해설🕵

문제 설명이 꼬임 없이 직관적이라 따로 설명할 것이 없다.

2. 생각의 흐름: 코드가 나오기까지 🗃️

(0) 완전 탐색은 제대로 된 풀이가 아니다.

만약 문자열 중 2개를 골라, 앞에서부터 단어가 몇 개나 같은지를 전부 확인 으로 문제를 풀었다면, SOLVED는 되겠지만 답이 아니다. 왜냐하면, 단어의 개수는 최대 20,000 이고, 단어의 길이는 최대 100 이다. 따라서 조합으로 2개 골라서 대조로 풀었다면, 시간 복잡도는 O($ n\choose 2 $* 100) 즉 200억이 나온다.

이러한 완탐도 정답이 되는 이유는 아직 대량의 데이터를 입력으로 넣는 TC가 없는 모양이다.
https://www.acmicpc.net/board/view/94785
여기서 나오는 TC가 돌아가야 한다.

(1) IDEA 도출💡

KEY WORD: Tri

접두사 문제답게 Tri를 먼저 떠올렸다. 하지만 전형적인 Tri라기 보단, 문제를 위해 조금 구조를 변형해야 한다.

    private static class Node {
        HashMap<Character,Node> children;
        int word_idx;

        public Node(int idx){
            children = new HashMap<>();
            this.word_idx = idx;
        }
    }

위는 Tri의 Node를 나타내는 Class이다.
여기서 children은 다음 문자를 나타내는 자식 노드를 뜻한다. word_idx는 해당 노드를 처음으로 트라이에 만든 문자열의 index를 뜻한다. 예를 들어 ["ab", "ac"]라는 입력이 들어왔다고 쳐보자. 그렇다면 "ab"의 index = 0, ac의 index = 1일 것이다.

그럼 위와 같은 구조로 Tri에 저장될 것이고, 각 노드의 word_idx는 다음과 같을 것이다.

먼저 a와 b 노드가 만들어지고, word_idx = 0으로 초기화 되었다. 이후 ac 문자열이 들어오면서, depth = 1인 a는 이미 존재했으므로 넘어가고, c가 새로 생기면서 word_idx = 1이 되는 것이다. 이렇게 해주는 이유는 (1) 답이 될 두가지 문자열 중 누가 먼저인지 확인과 (2) 현재 확인 중인 문자열의 접두사 길이와 이전까지의 계산 중 최대 접두사의 길이가 같을 때, Node가 만들어진 순서를 확인하여, 답이 될 문자열을 정하기 위해서 이다.
마치 단층으로 지질학적 연대기를 측정하는 것처럼 우리는 word_idx를 보고 해당 노드가 만들어진 시점을 알 수 있는 것이다.

(2) SUDO CODE 📜

• 0️⃣ 하나의 문자열을 받아, a. 트라이에 삽입 , b. 현 입력 문자열과 선두 문자가 최대한 많이 같은 문자열 찾기 를 동시에 진행할 것이다.
• 1️⃣ 문자열을 입력 받아 tri의 insert 함수에 넣는다.
• 2️⃣ 문자열의 문자 하나를 확인한다. (root의 자식노드에 값을 집어넣는 것이 시작점 임으로 우리는 항상 현재 문자열을 조회 중인 노드의 자식노드에 집어넣게 된다.)
• 3️⃣ 해당 문자가 현 노드의 자식노드로 이미 존재하는지 확인한다.
  • 3-1) 존재하지 않는다면, 자식 노드에 현 문자를 집어넣는다.
  • 3-2) 이미 존재한다면, 지금 도착한 트라이의 깊이(== 접두사의 길이)가 현재까지 가장 길었던 접두사의 길이보다 큰지 확인한다.
• 4️⃣ 현 트라이 깊이가 더 크거나 같고, 현재 삽입 중인 문자열이 기존에 들어간 문자열과 다른 단어라면, 다음을 진행한다.
  • 4-1) 현 트라이의 깊이(== 현재 공통 접두사 길이) > 현재까지 가장 길었던 접두사 길이(이하 MAX)
    MAX 갱신, 첫번째 답 = 노드의 word_idx가 가리키는 문자열 (먼저 삽입된 값), 두번째 답 = 현재 삽입 중인 문자열
  • 4-2) 현 트라이 깊이 == MAX
    현재 확인 중인 노드가 처음 만들어진 시기가 답으로 적어넣은 문자열이 만들어진 시기보다 빠르다면, 답 2개를 4-1처럼 갱신한다.
• 5️⃣ 삽입을 다 끝내면, 이미 ans 2개가 원하는 값으로 적혀있다.
  (예외 처리 - 어떤 문자열도 접두사가 하나라도 같은 게 없다면, 맨 처음, 그 다음 입력을 답으로 적어 낸다.)

(3) 시간복잡도 분석 🕓

문자열의 개수: N, 문자열의 길이: L

한번의 트라이 완성으로 모든 계산이 끝난다.
: $O(NL)$

20,000 * 100 = 2,000,000 (연산 횟수: 200만)

3. 구현 코드 🔎

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.StringTokenizer;
import java.util.TreeMap;


public class Main {
    private static class Node {
        HashMap<Character,Node> children;
        int word_idx;            // 해당 노드를 만들어낸 문자열의 index

        public Node(int idx){
            children = new HashMap<>();
            this.word_idx = idx;
        }
    }

    private static class Tri {
        Node root = new Node(-1);

        public void insert(String str, int word_idx) {
            Node now = this.root;
            for (int i = 0; i < str.length(); i++) {
                char c = str.charAt(i);
                if(!now.children.containsKey(c)) now.children.put(c, new Node(word_idx));
                else {
                    // 현재 들어온 tri의 깊이가 지금까지의 최대값보다 크거나 같다.
                    // 현재 확인하려는 Node(다음 Node)를 저장시켰던 단어가 현재 보는 단어랑 같지 않다.
                    if(i >= Max && !str.equals(Words[now.children.get(c).word_idx])) {
                        if(i > Max) {
                            // MAX 갱신
                            Max = i;
                            // 첫번째 답은 현재 접두사가 같은 값 중 먼저 만들어진 녀석 (노드를 최초로 만든 문자열)
                            ans[0] = now.children.get(c).word_idx;
                            // 두번째 답은 현재 삽입 중인 문자열
                            ans[1] = word_idx;
                        } else if (i == Max) {
                            // 현 노드를 만든 문자열의 삽입 시점이 답으로 적혀있는 문자열의 삽입 시점보다 빠르면 답을 갱신한다.
                            if(now.children.get(c).word_idx < ans[0]) {
                                ans[0] = now.children.get(c).word_idx;
                                ans[1] = word_idx;
                            }
                        }
                    }
                }
                now = now.children.get(c);
            }

        }
    }

    private static int [] ans = new int [2];
    private static String [] Words;
    private static int Max = -1;
    private static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        Words = new String[N];
        Tri tri = new Tri();
        for (int i = 0; i < N; i++) {
            Words[i] = br.readLine();
            tri.insert(Words[i], i);
        }

        if(Max == -1) {
            ans[0] = 0;
            ans[1] = 1;
        }

        System.out.println(Words[ans[0]]);
        System.out.println(Words[ans[1]]);
    }
}

4. 배운 것들 🎯

아직 트라이의 응용에 약한 듯 하다. 시간이 되면 관련 문제를 더 풀어봐야겠다.