(Python) - BOJ(5052번) : 전화번호 목록

https://www.acmicpc.net/problem/5052

5052번: 전화번호 목록

---

• 문제 : 

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

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

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

 

• 긴급전화: 911
• 상근: 97 625 999
• 선영: 91 12 54 26

 

이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다. 

 

 

 

---

• 풀이 :

입력받은 전화번호들에 대해 dictionary를 만들어준다. 

이후 모든 전화번호에 대해 1글자씩 뒤에 붙여가며 ( 911 이라면 9 -> 91 -> 911 의 순으로) dictionary에 있는지 확인해준다. 이 때, 911이라면 9 -> 91 -> 911에서 911은 반드시 dictionary에 존재하므로 이 경우는 제외하고 찾아주면 된다.

 

 

 

---

• 소스코드 : 

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    dic = dict()
    nums = list(input().strip().replace(" ", "") for _ in range(int(input())))
    for i in nums:
        dic[i] = 1
    flag = True
    for i in nums:
        s = ""
        for j in i:
            s += j
            if s in dic and s != i:
                print("NO")
                flag = False
                break
        if not flag:
            break
    if flag:
        print("YES")