[BaekJoon] 5670번 - 휴대폰 자판 [Java][C++]

문제 링크

---

1. 문제 풀이

자동 입력 기능을 구현할 때 전체 단어에 대한 평균 입력 횟수를 구해야 하는 문제로 트라이 자료구조를 활용하면 해결할 수 있다. 단어의 끝 여부와 자식 노드의 수를 저장하는 트라이에 각 단어들을 삽입한 후 DFS를 돌면 되는데 버튼을 눌러야 하는 순간은 현재 노드가 루트일 때나 현재 노드가 단어의 끝일 때, 또는 현재 노드가 둘 이상의 자식을 가질 때다.

---

2. 코드

1. 풀이 [Java]

메모리 제한이 약간 빡빡해서 클래스 기반으로 구현했다.

import java.io.*;

public class Main {

    static class Trie {

        static class Node {
            Node[] children = new Node[26];
            boolean isEnd;
            int cnt;  // 자식 노드의 수
        }

        Node root = new Node();

        void insert(String s) {
            Node cur = root;
            for (char c : s.toCharArray()) {
                int idx = c - 'a';
                if (cur.children[idx] == null) {
                    cur.children[idx] = new Node();
                    cur.cnt++;
                }
                cur = cur.children[idx];
            }
            cur.isEnd = true;
        }

        void solve() {
            solve(root, 0);
        }

        void solve(Node cur, int value) {
            if (cur.isEnd) {
                sum += value;
            }

            for (Node nxt : cur.children) {
                if (nxt == null) continue;

                if (cur == root || cur.isEnd || cur.cnt > 1) {
                    solve(nxt, value + 1);
                } else {
                    solve(nxt, value);
                }
            }
        }
    }

    static int sum;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String line;
        while ((line = br.readLine()) != null) {
            Trie trie = new Trie();
            sum = 0;

            int n = Integer.parseInt(line);
            for (int i = 0; i < n; i++) {
                trie.insert(br.readLine());
            }

            trie.solve();
            System.out.printf("%.2f\n", (double) sum / n);
        }
    }
}

2. 풀이 [C++]

#include <bits/stdc++.h>
using namespace std;

const int MX = 1 + 1000000;
const int ROOT = 0;
int unused;
int nxt[MX][26];
bool chk[MX];
int cnt[MX];  // 자식 노드의 수
int sum;

void init() {
    unused = ROOT + 1;
    memset(nxt, 0, sizeof(nxt));
    memset(chk, 0, sizeof(chk));
    memset(cnt, 0, sizeof(cnt));
    sum = 0;
}

void insert(string& s) {
    int cur = ROOT;
    for (char c : s) {
        int idx = c - 'a';
        if (nxt[cur][idx] == 0) {
            nxt[cur][idx] = unused++;
            cnt[cur]++;
        }
        cur = nxt[cur][idx];
    }
    chk[cur] = true;
}

void solve(int cur, int value) {
    if (chk[cur]) {
        sum += value;
    }

    for (int i = 0; i < 26; i++) {
        if (nxt[cur][i] == 0) continue;

        if (cur == ROOT || chk[cur] || cnt[cur] > 1) {
            solve(nxt[cur][i], value + 1);
        } else {
            solve(nxt[cur][i], value);
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    while (cin >> n) {
        init();

        for (int i = 0; i < n; i++) {
            string s;
            cin >> s;
            insert(s);
        }

        solve(ROOT, 0);
        cout << fixed << setprecision(2) << (double)sum / n << '\n';
    }
}

---