문제:
전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.
전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.
예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자.
- 긴급전화 : 911
- 상근 : 97 625 999
- 선영 : 91 12 54 26
이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.
입력:
첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1<=t<=50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1<=n<=10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화 번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.
출력:
각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.
풀이방법:
이전에 프로그래머스에서 이 문제를 풀었었지만, 그 때에는 단순히 반복문을 사용해서 풀었다면 이번에는 문자열에서 비교하는 자료구조인 Trie를 사용하도록 한다.
정보를 담을 Node 클래스와 이 Node들로 이루어진 Trie 클래스를 사용한다. Node의 key에는 알파벳, char 하나의 값이 들어가고, terminate는 이 Node가 마지막인지, 즉 string의 마지막인지를 나타내는 boolean 값이다. children은 더 이동할 수 있는 곳을 나타낸다.
함수로는 insert와 search 두 개가 있다. insert로 전화번호를 넣어주고 search로 일관성을 파악하도록 한다.
|
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
|
class Node(object):
def __init__(self,key,flag=False):
self.key = key
self.terminate = flag
self.children = {}
class Trie(object):
def __init__(self):
self.root = Node(None)
def insert(self,string):
currNode = self.root
for char in string:
if char not in currNode.children:
currNode.children[char] = Node(char)
currNode.terminate = False
currNode = currNode.children[char]
currNode.terminate = True
def search(self,string):
currNode = self.root
for char in string:
if char in currNode.children:
currNode = currNode.children[char]
else:
return False
if currNode.terminate:
return True
else:
return False
t=int(input())
for _ in range(t):
numberList = []
n=int(input())
for _ in range(n):
numberList.append(input())
numberList.sort()
Tree = Trie()
for number in numberList:
Tree.insert(number)
endFlag=True
for number in numberList:
if not Tree.search(number):
print("NO")
endFlag=False
break
if endFlag:
print("YES")
|
cs |
문제링크:
https://www.acmicpc.net/problem/5052
5052번: 전화번호 목록
문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없�
www.acmicpc.net
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]5525. IOIOI (0) | 2020.06.30 |
|---|---|
| [BOJ]11652. 카드 (0) | 2020.06.25 |
| [BOJ]12865. 평범한 배낭 (0) | 2020.06.18 |
| [BOJ]10830. 행렬 제곱 (0) | 2020.06.16 |
| [BOJ]1837. 암호제작 (0) | 2020.06.11 |