FilesExpand file tree

 main

/

P62_1.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

77 lines (70 loc) · 3 KB

 main

/

P62_1.java

Copy path

Top

File metadata and controls

• Code
• Blame

77 lines (70 loc) · 3 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

package ch16;

public class P62_1 {

// 트라이의 노드

class TrieNode {

// 단어 완성 여부

boolean word;

// 트라이의 자식 노드들

TrieNode[] children;

public TrieNode() {

// 문제 제약 조건에 따라 소문자 알파벳으로 구성되므로 자식 노드는 알파벳의 개수인 최대 26개까지 가능

children = new TrieNode[26];

word = false;

}

}

class Trie {

TrieNode root;

// 클래스 생성시 루트로 빈 트라이 노드 생성

public Trie() {

root = new TrieNode();

}

// 단어 삽입

public void insert(String word) {

// 루트부터 시작

TrieNode cur = root;

// 단어의 문자를 차례대로 반복하며 자식 노드 구성

for (char c : word.toCharArray()) {

// 해당 문자의 자식 노드가 존재하지 않으면 신규 트라이 노드 생성

// 'a'가 인덱스 0, 'z'는 인덱스 25가 된다.

if (cur.children[c - 'a'] == null) {

cur.children[c - 'a'] = new TrieNode();

}

// 자식 노드를 현재 노드로 교체

cur = cur.children[c - 'a'];

}

// 단어가 완성된 후이므로 현재 노드는 단어 완성 여부에 true 설정

cur.word = true;

}

// 단어 존재 여부 판별

public boolean search(String word) {

// 루트부터 시작

TrieNode cur = root;

// 단어의 문자를 차례대로 반복하며 자식 노드 구성

for (char c : word.toCharArray()) {

// 자식 노드가 존재하지 않으면 false 리턴

if (cur.children[c - 'a'] == null)

return false;

// 자식 노드를 현재 노드로 교체

cur = cur.children[c - 'a'];

}

// 탐색이 종료된 후 단어 완성 여부를 리턴

// 완성된 단어가 아니라면 문자는 모두 매칭이 되어도 단어 완성 여부는 false일 수 있음

return cur.word == true;

}

// 문자열로 시작 단어 존재 여부 판별

public boolean startsWith(String prefix) {

// 루트부터 시작

TrieNode cur = root;

// 단어의 문자를 차례대로 반복하며 자식 노드 구성

for (char c : prefix.toCharArray()) {

// 자식 노드가 존재하지 않으면 false 리턴

if (cur.children[c - 'a'] == null)

return false;

// 자식 노드를 현재 노드로 교체

cur = cur.children[c - 'a'];

}

// 탐색이 종료되면 항상 true 리턴, 시작 여부만 판별하면 되므로 단어 완성 여부가 false여도 관계없음

return true;

}

}

}