[Algorithm] C++/Python 백준 5670번: 휴대폰 자판

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

// 42jerrykim.github.io에서 더 많은 정보를 확인할 수 있다
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <cstdio>

using namespace std;

// Trie의 노드를 나타내는 구조체
struct TrieNode {
    bool is_end;               // 이 노드가 단어의 끝인지 표시
    int child_count;           // 자식 노드의 수
    TrieNode* children[26];    // 알파벳 소문자에 대한 자식 노드 포인터 배열

    // 생성자: 초기화
    TrieNode() {
        is_end = false;
        child_count = 0;
        memset(children, 0, sizeof(children));
    }
};

// 단어를 Trie에 삽입하는 함수
void insert(TrieNode* root, const string& word) {
    TrieNode* node = root;
    for (char c : word) {
        int idx = c - 'a';  // 알파벳을 인덱스로 변환
        if (!node->children[idx]) {
            node->children[idx] = new TrieNode();  // 자식 노드가 없으면 생성
            node->child_count++;                   // 자식 수 증가
        }
        node = node->children[idx];  // 다음 노드로 이동
    }
    node->is_end = true;  // 단어의 끝 표시
}

// 단어를 입력하는 데 필요한 버튼 횟수를 계산하는 함수
int count_key_presses(TrieNode* root, const string& word) {
    int key_presses = 1;  // 첫 번째 문자는 항상 입력해야 함
    TrieNode* node = root->children[word[0] - 'a'];  // 첫 번째 문자로 이동
    for (size_t i = 1; i < word.length(); ++i) {
        int idx = word[i] - 'a';
        // 현재 노드가 단어의 끝이거나 자식이 둘 이상이면 버튼 입력 필요
        if (node->is_end || node->child_count > 1) {
            key_presses++;
        }
        node = node->children[idx];  // 다음 노드로 이동
    }
    return key_presses;
}

// Trie를 동적 할당 해제하는 함수
void delete_trie(TrieNode* node) {
    if (!node) return;
    for (int i = 0; i < 26; ++i) {
        if (node->children[i]) {
            delete_trie(node->children[i]);  // 자식 노드들을 재귀적으로 삭제
        }
    }
    delete node;  // 현재 노드 삭제
}

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

    int N;
    while (cin >> N) {
        vector<string> words(N);
        for (int i = 0; i < N; ++i) {
            cin >> words[i];  // 단어 입력
        }

        TrieNode* root = new TrieNode();  // Trie의 루트 노드 생성

        for (const string& word : words) {
            insert(root, word);  // 단어들을 Trie에 삽입
        }

        int total_presses = 0;
        for (const string& word : words) {
            total_presses += count_key_presses(root, word);  // 각 단어의 버튼 입력 횟수 계산
        }

        double average_presses = (double)total_presses / N + 1e-8;  // 평균 계산 및 부동소수점 보정
        printf("%.2f\n", average_presses);  // 소수점 둘째 자리까지 출력

        delete_trie(root);  // Trie 메모리 해제
    }

    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

# 42jerrykim.github.io에서 더 많은 정보를 확인할 수 있다
import sys
input = sys.stdin
print = sys.stdout.write

import decimal
ctx = decimal.getcontext()
ctx.rounding = decimal.ROUND_HALF_UP

def solve(N, words):
    depths = [0] * N  # 각 단어의 버튼 입력 횟수를 저장할 리스트

    def init(indices, i, depth):
        # indices: 현재 처리 중인 단어들의 인덱스 리스트
        # i: 현재 검사할 문자 위치 (0부터 시작)
        # depth: 현재까지 버튼을 누른 횟수
        wordbook = dict()
        for idx in indices:
            if len(words[idx]) == i:
                depths[idx] = depth  # 단어의 끝에 도달하면 깊이 저장
                continue
            c = words[idx][i]
            if c in wordbook:
                wordbook[c].append(idx)
            else:
                wordbook[c] = [idx]

        for c, subindices in wordbook.items():
            # 공통된 문자를 최대한 건너뛰기 위해 j를 사용
            j = i + 1
            while True:
                # 단어의 길이를 넘어가면 중지
                if any(len(words[idx]) == j for idx in subindices):
                    break
                # 다음 문자가 모두 같은지 확인
                target = words[subindices[0]][j]
                if any(words[idx][j] != target for idx in subindices):
                    break
                j += 1

            # 끝에 도달한 단어는 깊이 저장
            subsub = []
            for idx in subindices:
                if len(words[idx]) == j:
                    depths[idx] = depth + 1
                else:
                    subsub.append(idx)

            # 남은 단어들에 대해 재귀적으로 처리
            if subsub:
                init(subsub, j, depth + 1)

    init(range(N), 0, 0)

    # 평균 버튼 입력 횟수 계산
    return (decimal.Decimal(sum(depths)) / N).quantize(decimal.Decimal('0.01'))

while True:
    try:
        N = int(input.readline().strip())
        words = [input.readline().strip() for _ in range(N)]
        ans = solve(N, words)
        print(f"{ans}\n")
    except (EOFError, ValueError):  # 입력 끝에서 빈 줄 -> int() 실패
        break