백준 5052 - 전화번호 목록

문제

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

풀이

문제에서 전화번호 목록이 주어지면 목록에 있는 전화번호들은 번호가 겹쳐지면 안되는 문제,
각 번호들이 겹쳐지는지 아닌지 확인해야하는 문제 절대 짧은 문자를 기준으로 겹쳐지는 것을 찾는 것이 아니다!!

접근 1)

하나씩 전부 비교한다. 하나씩 전부 비교하게 된다면 O(N^2)의 시간이 필요하다. => 시간초과

접근 2)

전화번호를 오름차순으로 정렬한다.
파이썬에서 문자열을 오름차순으로 정렬하게 된다면 문자 하나하나씩 아스키코드로 비교하고 그래도 같다면 문자 길이로 정렬한다. 예를 들면 [911,9112345] 리스트가 있다면 911까지 비교하고 그 뒤로 길이순서대로 정렬한다. 만약 [9112346,9112345] 리스트라면 [9112345,9112346]으로 정렬 될 것이다.
이렇게 된다면 앞부분이 겹쳐지는 부분을 우선으로 정렬하고 그 다음 정렬조건으로 길이로 비교하게된다.
이렇게 정렬하게 된다면 O(N)으로 겹쳐지는 전화번호가 있는지 없는지 파악 할 수 있다.

소스코드

import sys
from collections import deque

def checker_string(string_arr:deque):
    for i in range(1,len(string_arr)):
        tmp1 = string_arr[i]
        tmp2 = string_arr[i-1]
        if tmp1.startswith(tmp2):
            return False
    return True

for tc in range(int(sys.stdin.readline())):
    n = int(sys.stdin.readline())
    string_arr = deque()
    for i in range(n):
        string_arr.append(sys.stdin.readline().rstrip())
    string_arr = deque(sorted(string_arr))
    if checker_string(string_arr):
        print("YES")
    else:
        print("NO")