[자바] 백준 5670 - 휴대폰 자판 (boj java)

문제 : boj5670

 

  너무 대놓고 Trie 써야할것같이 생긴 문제였다. 사실 플래라곤 하지만 Trie 자료구조를 알고 있다면 별 문제 없이 풀 수 있는 기본 형태의 문제이다. 예를들어 'hello, hell, heaven, goodbye'를 Trie에 담아보면 다음과 같이 생겼다. 다음과 같이 소문자 하나씩 트리 구조로 유지하는 형태의 자료구조이다(주황색은 단어의 끝이 존재함을 의미한다.). 문자열 쪽으론 유명한 알고리즘이라 검색해보면 엄청 많이 나온다.

 

그럼 로직을 다음과 같이 구현하면 된다.

 

1. N개의 단어를 Trie 자료구조에 넣는다.

2. N개의 단어를 Trie 자료구조에서 찾으면서 주어진 조건에 따라 몇 번의 입력이 필요한지 센다.

3. '2'를 전부 더한다.

 

좀 더 효율적으로 하려면

 

1. N개의 단어를 Trie 자료구조에 넣는다.

2. 현재 단어의 끝인지 여부와 자식 노드의 수를 가지고 Trie 전체를 dfs 하면서 몇 번의 입력이 필요한지 센다.

 

처럼 진행하면 된다. 이하 코드는 후자의 방식으로 짰다. 전자로도 시간은 더 걸리지만 통과는 되도록 설정해둔 다소 널널한 문제이다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

class Trie {
    boolean isWordEnd;
    Trie[] child;
    int childCnt;

    public Trie() {
        isWordEnd = false;
        child = new Trie[26];
        childCnt = 0;
    }

    public Trie addAndGetChild(char c) {
        if (child[c-'a'] == null) {
            child[c - 'a'] = new Trie();
            childCnt++;
        }
        return child[c-'a'];
    }

    public void setWordEnd() {
        this.isWordEnd = true;
    }
}

public class Main {
    Trie trie;
    int cntSum;
    private void insert(String s) {
        Trie iter = trie;
        for (int i = 0; i < s.length(); i++) {
            iter = iter.addAndGetChild(s.charAt(i));
        }
        iter.setWordEnd();
    }

    private void proc(Trie iter, int cnt) {
        if (iter.isWordEnd) {
            cntSum += cnt;
        }
        for (int i = 0; i < 26; i++) {
            if (iter.child[i] == null) continue;
            proc(iter.child[i], iter.childCnt==1?(iter.isWordEnd?cnt+1:cnt):cnt+1);
        }
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        while (true) {
            String s = br.readLine();
            if (s == null) break;
            trie = new Trie();
            cntSum = 0;
            int n = Integer.parseInt(s);
            for (int i = 0; i < n; i++) {
                insert(br.readLine());
            }
            for (int i = 0; i < 26; i++) {
                if (trie.child[i] == null) continue;
                proc(trie.child[i], 1);
            }
            sb.append(String.format("%.2f\n", 1d*cntSum/n));
        }
        System.out.print(sb);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}