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

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

5052번: 전화번호 목록

문제를 보고 전화번호를 길이를 기준으로 정렬한 후 더 긴 번호와 접두어를 비교하는 방법을 생각했다.

적용해 보았다.

 

t = int(input())

answer = []

for i in range(t):
    flag = "YES"
    n = int(input())
    call_list = []
    for j in range(n):
        call_num = str(input())
        call_list.append(call_num)
    
    call_list = sorted(call_list, key=lambda x : len(x))
    
    for j in range(n):
        length = len(call_list[j])

        for k in range(j+1, n):
            if(call_list[j] == call_list[k][:length]):
                flag = "NO"
        
        if(flag == 'NO') : break

    answer.append(flag)

for i in range(t):
    print(answer[i])

 

시간 초과가 되었다.

---

import sys

def checking():
    for j in range(len(call_list) -1):
        if(call_list[j] == call_list[j+1][:len(call_list[j])]) :
            print("NO")
            return
    print("YES")
    return

t = int(input())

for i in range(t):
    n = int(input())
    call_list = []
    for j in range(n):
        call_num = sys.stdin.readline().strip()
        call_list.append(call_num)
     
    call_list.sort()
    checking()

 

개선 사항

1. input() 함수 대신 sys.stdin.readline() 사용

2. 길이 기준으로 정렬이 아닌 사전 순으로 정렬 후 다음 번호만 비교

 

#변경 전 방법
call_list = sorted(call_list, key=lambda x: len(x))
#변경 후
call_list.sort()

 

위 두 방법을 적용하니 시간 초과 문제가 해결되었다.

 

python을 이용해 문제를 많이 풀어야겠다는 생각이 들었다.

---

참고 코드

https://chldkato.tistory.com/83 

https://sinsomi.tistory.com/entry/%EB%B0%B1%EC%A4%80-Python-%EC%A0%84%ED%99%94%EB%B2%88%ED%98%B8-%EB%AA%A9%EB%A1%9D-%EC%B4%88%EC%BD%94%EB%8D%94