PS/Python
[백준] 5052- 전화번호 목록 (파이썬, Python)
w00se
2020. 7. 21. 14:46
https://www.acmicpc.net/problem/5052
5052번: 전화번호 목록
문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없�
www.acmicpc.net
문제를 보고 전화번호를 길이를 기준으로 정렬한 후 더 긴 번호와 접두어를 비교하는 방법을 생각했다.
적용해 보았다.
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을 이용해 문제를 많이 풀어야겠다는 생각이 들었다.
참고 코드