[BOJ/Python] 5052. 전화번호 목록

📌 문제

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

5052번: 전화번호 목록

 

📌 문제 접근 방법

1. 처음에는 입력 받은 번호를 정렬시키고 하나씩 비교하면서 다른 숫자를 찾았다.
   될 줄 알았는데 n이 10000까지 입력가능하니까 최악의 경우엔 1초를 넘긴다.
2. 그래서 코드를 갈아엎었다!
   인덱스를 초기에 0으로 설정해놓고 모든 문자열을 순회하면서 해당 인덱스의 값을 key로, 해당 문자열을 value로 해서 temp에 넣는다.
3. temp의 value중에서 길이가 2보다 크다면 해당 인덱스까지 숫자가 같은 문자열이 있다는 뜻이고,
   그 value 리스트 안에 인덱스가 (문자열길이 - 1)인 문자열이 있다면 이 문자열을 제외한 리스트 안의 다른 문자열은 전화를 걸 수 없게 되므로 answer를 NO로 바꾸고 return 시켜준다.

 

📌 코드

# 백준 5052 전화번호 목록

def is_same(num1, num2):
    n = min(len(num1), len(num2))

    for i in range(n):
        if num1[i] != num2[i]:
            return True

    return False


def can_cailling():
    for i in range(N):
        for j in range(i+1, N):
            flag = is_same(numbers[i], numbers[j])

            if not flag:
                return 'NO'

    return 'YES'


for _ in range(int(input())):
    N = int(input())
    numbers = [input() for _ in range(N)]

    numbers.sort()

    print(can_cailling())

-> 시간초과

 

# 백준 5052 전화번호 목록
import sys
from collections import defaultdict

input = sys.stdin.readline

def can_cailling(numbers, idx):
    global answer

    temp = defaultdict(list)
    check = []

    for number in numbers:
        if len(number) > idx:
            temp[number[idx]].append(number)

            if len(number) == idx+1:
                check.append(number[idx])

    for key, lst in temp.items():
        if len(lst) > 1:
            if key in check:
                answer = 'NO'
                return

            can_cailling(lst, idx+1)


for _ in range(int(input())):
    N = int(input())
    numbers = [input().strip() for _ in range(N)]

    answer = 'YES'
    can_cailling(numbers, 0)

    print(answer)