[Python Algorithm] 전화번호 목록 BOJ #5052

문제

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

5052번: 전화번호 목록

 

내 문제 풀이

import sys

t = int(sys.stdin.readline().strip())
for _ in range(t):
    n = int(sys.stdin.readline().strip())
    nums = []
    for _ in range(n):
        nums.append(sys.stdin.readline().strip())
    nums.sort()
    check = True

    for i in range(0, n-1):
        if nums[i] == nums[i+1][:len(nums[i])]:
            check = False
            break

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

👉 문자열 문제

전화번호들이 저장된 nums 리스트를 정렬하면, 당연하게도 접두사가 비슷한 순으로 정렬된다.

따라서 굳이 전부를 비교해주지 않아도, 앞뒤 번호끼리만 비교해줘도 충분하다.

 

💡 피드백

처음엔 2중 for문으로 일일이 비교해주었는데, 시간초과가 발생했다.

이런 접두사, 접미사 문제들같은 경우에는 비교를 효율적으로 할 방법을 빨리 찾아주는게 중요할듯 하다.