Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

34. 문자열 알고리즘 1

KMP 알고리즘과 트라이 자료구조를 다뤄 봅시다.

7. 휴대폰 자판

5670번

조금 어려운 문제

이번 문제는 사전 내에서 가능한 다음 글자가 하나뿐이라면 그 글자를 버튼 입력 없이 자동으로 입력해 주는 모듈을 사용하면서 단어를 입력하기 위해 버튼을 눌러야 하는 횟수의 평균을 구하는 문제이다.

트라이 클래스를 이용한다. 주어진 단어들을 트라이 구조에 넣은후 찾고자 하는 단어를 입력할때 현재 노드의 자식 노드가 하나밖에 없다면,이는 특정 문자 다음에 오는 문자가 하나밖에 없다는 뜻과 같다는 점 등을 고려하여 구현한다.

Java / Python

• Java

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		String str;

		while ((str = br.readLine()) != null) {
			int N = Integer.valueOf(str);
			List<String> list = new ArrayList<String>();
			Trie trie = new Trie();
			double answer = 0;

			for (int i = 0; i < N; i++) {
				String word = br.readLine(); // 입력 받기
				list.add(word);
				trie.insert(word);
			}

			for (String l : list) {
				answer += trie.contains(l);
			}

			// 평균 출력
			sb.append(String.format("%.2f", answer / N)).append("\n");
		}

		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}

	static class Trie {
		public TrieNode root;

		Trie() {
			this.root = new TrieNode();
		}

		public void insert(String word) {
			TrieNode tempNode = this.root;

			for (int i = 0; i < word.length(); i++) {
				tempNode = tempNode.getChildNodes().computeIfAbsent(word.charAt(i), c -> new TrieNode());
			}

			tempNode.setLastChar(true);
		}

		public int contains(String word) { // 존재 여부
			TrieNode tempNode = this.root;
			int cnt = 1;

			tempNode = tempNode.getChildNodes().get(word.charAt(0));

			for (int i = 1; i < word.length(); i++) {
				if (tempNode.getChildNodes().size() >= 2) {
					cnt++;
				}

				else if (tempNode.getChildNodes().size() == 1 && tempNode.isLastChar()) {
					cnt++;
				}

				char ch = word.charAt(i);
				TrieNode node = tempNode.getChildNodes().get(ch);

				tempNode = node;
			}

			return cnt;
		}
	}

	static class TrieNode {
		private Map<Character, TrieNode> childNode = new HashMap<>();
		private boolean isLastChar;

		public boolean isLastChar() { // 마지막 문자 확인
			return this.isLastChar;
		}

		public void setLastChar(boolean isLastChar) {
			this.isLastChar = isLastChar;
		}

		public Map<Character, TrieNode> getChildNodes() {
			return this.childNode;
		}
	}
}

• Python

import sys
 
class Node:
    def __init__(self,chr):
        self.chr = chr
        self.child = {}
        self.check = False

class Trie:
    def __init__(self):
        self.root = Node('')

    def insert(self, word):
        node = self.root
        for w in word:
            if w not in node.child:
                new = Node(w)
                node.child[w] = new
                node = new
            else:
                node = node.child[w]
        node.check = True

    def contains(self, word):
        cnt = 0
        cur = self.root
        for w in word:
            cur = cur.child[w]
            if len(cur.child) > 1 or cur.check:
                cnt+=1
        return cnt

while 1:
    t = Trie()
    words = []
    try: N = int(sys.stdin.readline())
    except: break

    for _ in range(N):
        s = sys.stdin.readline().rstrip()
        t.insert(s)
        words.append(s)
    result = 0
    for word in words:
        result += t.contains(word)

    print("%.2f" % (result/N))