[백준] 5052 전화번호 목록

📌문제 링크

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

💡 문제 풀이

전화번호를 정렬하는데 비슷한 번호, 같은 수로 시작하는 번호끼리 붙어있어야 하니까 문자열로 정렬한다는 것까진 생각했다
근데 이중for문을 쓰는 방법(당연히 시간초과로 틀릴 방법) 말고는 접두어가 포함된 번호를 찾는 방법을 생각하지 못했다

그래서 구글링함ㅎㅎ
정렬했으니까 앞뒤 숫자만 비교해도 일관성이 있는지 없는지 찾아낼 수 있었다!

처음에 틀렸었는데 문자열 포함 in을 써서였다
그냥 포함되는 게 아니라 '접두어'가 같아야 한다...
ex) 1과 21은 접두어가 같진 않지만 1이 21에 포함됨

접두어가 같은지 찾기 위해 i번째 문자열 길이만큼만 비교했는데 in 말고 ==를 써도 될 것 같다

📋코드

# 5052 전화번호 목록
t = int(input())


# 구글링함...
# 정렬했으니까 앞뒤 숫자만 비교해도 다 찾을 수 있다!
def check_num():
    n = int(input())
    numbers = []
    check = 0
    for i in range(n):
        numbers.append(input())

    numbers.sort()
    # 틀린 이유... 그냥 포함관계가 아니라 "접두어"여야 한다!!
    for i in range(n-1):
        length = len(numbers[i])
        if numbers[i] in numbers[i+1][:length]:
            check = 1
            break

    if check == 1:
        print("NO")
    else:
        print("YES")


# 그냥 파이썬 특성상 함수 쓰면 빠르다니까 함수로 해줌
for _ in range(t):
    check_num()