BaekJook5052_전화번호 목록

문제

내 풀이 (시간초과)
처음 문제를 풀때 각 전화번호를 문자열로 입력받고 입력받은 문자열들을 문자열 길이로 정렬을 먼저 하였다. 그 뒤 각 문자열을 비교해가며 접두어가 있는지 없는지 확인해봤는데 시간초과로 틀렸다..

시간 초과로 틀린 코드

n = int(input())

for i in range(n):
   k = int(input())
   pl = []
   for j in range(k):
       pl.append(str(input())) # 전화번호를 문자열로 처리하기 위해 str로 받음
   pl.sort(key=lambda x : len(x)) # 받은 전화번호 리스트를 문자열 길이 순으로 정렬
   
   for i in range(len(pl)-1): 
       # 확인하는 문자열 i가 리스트의 다른 원소들의 접두어인지 확인하기 위한 변수 cnt
       check = True # 검사 중 한번이라도 원소가 접두어로 됐을 경우 반복문 탈출을 위한 변수
       cnt = 0
       for j in range(i+1,len(pl)):
           for k in range(len(pl[i])): # k는 위에서의 i의 길이만큼 순회
               if pl[i][k] == pl[j][k]: # 문자가 일치할 경우 cnt 1씩 증가
                   cnt += 1
               else: # 한번이라도 일치하지 않는경우는 검사할 필요 x
                   break
           if cnt == len(pl[i]): # 접두어가 있는 경우 이므로 check = False로 하고 반복문 탈출
               check = False
               break
           else:
               cnt = 0
       if check == False: # check가 false면 접두어가 있는경우 이므로 no 출력 후 반복문 탈출
           print('NO')
           break
   if check:    # 전체를 검사 후 check가 True면 접두어가 없으므로 yes
       print('YES')
           

다시 풀어본 결과..

중간에 불필요한 과정들을 전부 날리고 input()도 sys 라이브러리를 사용하여 최대한 시간을 줄여본 결과 겨우 시간 제한안에 문제를 풀었다. 탐색 시간을 더 효과적으로 줄이는 방법이 있을 것 같은데 나중에 다시 한번 공부하고 풀이 해봐야겠다.

정답 코드

import sys
input = sys.stdin.readline

n = int(input())

for i in range(n):
    k = int(input())
    pl = []
    for j in range(k):
        pl.append(input().strip())
    pl.sort() # 받은 전화번호 리스트 
    for i in range(len(pl)-1): 
        # 확인하는 i가 리스트의 다른 원소들의 접두어인지 확인하기 위한 변수 word
        check = True # 검사 중 한번이라도 원소가 접두어로 됐을 경우 반복문 탈출을 위한 변수
        word = pl[i]
        for j in range(i+1,len(pl)):
            if pl[i] == pl[j][:len(word)]: # 숫자 자릿수 만큼 비교 후 일치할 경우 check = False
                check = False
                break
        if check == False: # check가 false면 접두어가 있는경우 이므로 no 출력 후 반복문 탈출
            print('NO')
            break
    if check:    # 전체를 검사 후 check가 True면 접두어가 없으므로 yes
        print('YES')