BOJ#5670 휴대폰 자판



* 문제



* 풀이

카카오 블라인드 채용 - 3차 코딩테스트 5번 문제와 유사합니다.


Trie를 사용하여 풀어보았습니다. 


1. 모든 문자열을 Trie에 저장한 후

2. child의 개수가 2 이상인 경우, terminal 노드인데 child가 존재하는 경우를 카운트하였습니다.


부족한 점이 있으면 댓글로 알려주세요. 감사합니다.





* 나의 코드

https://github.com/stack07142/BOJ/blob/a3f55a12084c8b798e96dd86eedbdc8661595777/BOJ%235670/src/Main.java


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

public class Main {

static final int SIZE = 26;
static int cnt = 0;

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();

int N = Integer.parseInt(line);

String[] str = new String[N];

for (int i = 0; i < N; i++) {

str[i] = br.readLine();
trie.insert(str[i]);
}

for (int i = 0; i < SIZE; i++) {

if (trie.root.children[i] != null) {

trie.check(trie.root.children[i], 1);
}
}

System.out.printf("%.2f", (double) cnt / N);
System.out.println();

cnt = 0;
}


}
}

class Trie {

TrieNode root;

Trie() {

root = new TrieNode();
}

private int toNumber(char c) {

return c - 'a';
}

void insert(String key) {

int length = key.length();
TrieNode currentNode = root;

for (int i = 0; i < length; i++) {

int next = toNumber(key.charAt(i));

if (currentNode.children[next] == null) {

currentNode.children[next] = new TrieNode();
currentNode.nChild++;
}


currentNode = currentNode.children[next];
}

currentNode.isTerminal = true;
}

void check(TrieNode node, int ret) {

if (node.isTerminal) {

Main.cnt += ret;
}

if (node.nChild >= 2) {

ret++;
}

if (node.isTerminal && node.nChild == 1) {

ret++;
}

for (int i = 0; i < Main.SIZE; i++) {

if (node.children[i] != null) {

check(node.children[i], ret);
}
}

}
}

class TrieNode {

TrieNode[] children = new TrieNode[Main.SIZE];
boolean isTerminal;

int nChild = 0;

TrieNode() {

isTerminal = false;

for (int i = 0; i < Main.SIZE; i++) {

children[i] = null;
}
}
}



저작자 표시 비영리 동일 조건 변경 허락
신고

'Algorithm BOJ > 문자열' 카테고리의 다른 글

BOJ#5670 휴대폰 자판  (0) 2017.11.26
BOJ#5052 전화번호 목록  (0) 2017.11.25
BOJ#1152 단어의 개수  (0) 2017.05.22
BOJ#1254 팰린드롬 만들기  (0) 2017.03.31
BOJ#10942 팰린드롬?  (0) 2017.03.30
블로그 이미지

stack.07142

IT, Android, Java, Algorithm. Kotlin, Swift, iOS

댓글을 달아 주세요

티스토리 툴바