문제:

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.

전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자.

- 긴급전화 : 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

+ Recent posts