[python 백준 5052] 전화번호 목록

접근 방법

1. 숫자 갯수가 작은 순으로 정렬
2. 문자열로 변환
3. 정렬된 순서로 특정 전화번호와 다른 전화번호들을 비교(특정 전화번호 갯수까지 잘라서 그부분만 비교)
4. 같을 경우 YES 출력 후 종료
5. 다를 경우 3번 반복

실패 코드(시간초과)

import sys

t = int(sys.stdin.readline())

for i in range(t):
    n = int(sys.stdin.readline())

    phone_list = [int(sys.stdin.readline()) for i in range(n)]
    phone_list.sort()

    phone_list = list(map(str, phone_list))

    index = 0
    check = 0
    while index < n - 1:
        if check:
            break
        phone_num = phone_list[index]
        phone_len = len(phone_num)
        tmp = index + 1
        while tmp < n - 1:
            if phone_num == phone_list[tmp][:phone_len]:
                print("NO")
                check = 1
                break
            else:
                tmp += 1
        index += 1
    if check == 0:
        print("YES")

 

다른 사람들이 푼 것을 보니 정렬을 하면 바로 옆 문자열만 비교하면 됐던 문제다. (위 실패코드에서 두번째 while문 삭제)

정답코드 1

import sys

t = int(sys.stdin.readline())

for i in range(t):
    n = int(sys.stdin.readline())

    phone_list = [sys.stdin.readline().strip() for i in range(n)]
    phone_list.sort()

    index = 0
    check = 0

    while index < n - 1:
        phone_num = phone_list[index]
        phone_len = len(phone_num)

        if phone_num == phone_list[index + 1][:phone_len]:
            print("NO")
            check = 1
            break
        else:
            index += 1

    if check == 0:
        print("YES")

또한 이 문제는 Trie로 풀 수도 있다고 한다.

추후 업로드 예정

정답 코드 2