[파이썬] 5052번 : 전화번호 목록

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

5052번: 전화번호 목록

 

문제

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

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

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

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

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

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.

출력

각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.

예제 입력 1 복사

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

예제 출력 1 복사

NO
YES

 

생각

일단 for문을 많이 쓰게 된다면 좋지 않음을 인지 하였다.

입력과 동시에 검색을 하는 함수를 만들면 어떨까 하는 생각을 했다. 

그리고 숫자가 아닌 문자열로써 비교를 한다면 더 쉬울 것이라고 생각을 했다.

 

import sys


def search(data, store):
    for i in store:
        if len(data) < len(i):
            if data==i[:len(data)]:
                return True
        else:
            if i == data[:len(i)]:
                return True
    return False


total = list()
searched = False
for _ in range(int(sys.stdin.readline())):
    total = []
    searched = False
    for _ in range(int(sys.stdin.readline())):
        str_num = str(int(sys.stdin.readline()))
        if len(total) < 1:
            total.append(str_num)
        else:
            if (searched == False) and search(str_num, total):
                searched = True
            total.append(str_num)
    if searched:
        print("NO")
    else:
        print("YES")

그래서 처음에 시도했던 코드는 위의 코드이다.

그런데 시간초과가 났다. 하지만 코드를 작성하고 제출을 누를때에도 역시 시간초과가 될꺼라고 예상은 했다. 하지만 더이상 생각이 나지 않아 제출하였었다.

 

다른풀이를 찾아보다가

정렬을 해서 앞뒤의 것을 비교하면 되는 구나를 알게 되었다.

즉 나는 문자열로접근을 했는데 일단 테스트케이스에 대한 것을 다 입력 받은 후 문자열의 sort함수로 정렬을 하게 된다면

911
97625999
91125426

순으로 입력을 해도

911
91125426
97625999

순으로 정렬이 된다는 것을 깨닫게 되었고 내가 적었었던 코드와 더불어 생각을 하게 되면 쉽게 풀렸다.

그래서 정렬이 된 문자열을 가지고 앞 뒤의 것을 비교하는데에 있어서 길이가 다르다 이때 길이는 작은 것을 사용해야하

므로 길이는 앞의 인덱스에 해당하는 것을 사용하면 된다. -> 이것이 핵심이다.

import sys
for _ in range(int(sys.stdin.readline())):
    searched = False
    nums=[sys.stdin.readline().strip() for _ in range(int(sys.stdin.readline()))]
    nums.sort()
    for i in range(len(nums)-1):
        min_length=len(nums[i])
        if nums[i]==nums[i+1][:min_length]:
            searched=True
            break
    if searched:
        print("NO")
    else:
        print("YES")

위에서 하나의 flag인 searched에 해당하는 것을 설정해두어서 만약 같은 문자를 찾았을 경우 True가 되는 성질을 이용해 No와 YES를 출력하게 했다.

 

핵심

문자열을 정렬하면 사전 순으로 정렬이 된다!