[백준] 5052 전화번호 목록 (파이썬 python)

 

 

문제 링크

 

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

5052번: 전화번호 목록

 

 

 

문제 풀이

 

이중 for문으로 하나하나 일치 여부를 확인하기에는 전화번호 개수 범위가 최대 10000개까지로

시간 초과 가능성이 높았습니다.

그래서 비교 횟수를 최소화하는 방법을 고민하던 중, 문자열의 정렬 원리를 통해 해결했습니다.

문자열은 대소비교를 통해 정렬되는 숫자와 달리 앞에서부터 비교되어 정렬됩니다.

 

예를 들어 아래 숫자를

311
27625999
31125426

 

문자열을 기준으로 정렬할 경우

27625999

311

31125426

다음과 같이 정렬되어, 일치되는 문자가 접두어로 있을 경우 바로 앞뒤로 정렬됩니다.

결국 문자열 정렬을 한 뒤 전체 인덱스에 대해 앞뒤 비교만 해주면 되는 것입니다.

 

전체 코드

 

def check(nums):
    for i in range(len(nums) - 1):
        if nums[i] == nums[i + 1][:len(nums[i])]:
            return False
    return True

t = int(input())
for _ in range(t):
    n = int(input())
    nums = []
    for _ in range(n):
        nums.append(str(input().rstrip()))
    nums.sort()
    if check(nums):
        print("YES")
    else:
        print("NO")