알고리즘/백준
[백준 / Python] 5052번 전화번호 목록 | 초코더
cloud_nice
2020. 1. 14. 00:14
https://www.acmicpc.net/problem/5052
5052번: 전화번호 목록
문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다. 예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자 긴급전화: 911 상근: 97 625 999 선영: 91 12 54 26 이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가
www.acmicpc.net
접근법
numbers배열에 전화번호 목록을 입력받아옵니다. 그리고 정렬시킵니다.
문자열을 정렬시키면 ['911', '97625999', '91125426'] 이런식으로 사전순으로 정렬되므로 비교해줄때 i번째와 i+1번째만 비교(붙어있는 문자열끼리만 비교해도 접두어가 겹치는지 알수있음)합니다.
저는 numbers를 입력받을때 input()함수를 썼는데 시간초과가 떠서 이제 sys.stdin.readline()함수를 사용해서 한줄씩 입력받아오는 것을 습관들이겠습니다.
numbers.append(sys.stdin.readline().strip())을 하고 numbers를 출력해보면 ['911\n', '97625999\n', '91125426\n']입니다. 개행문자를 제거해주기위해 strip()함수를 사용하였습니다.
나의 풀이
import sys
def solution(numbers):
numbers.sort() #numbers 정렬시키면 사전순으로 정렬
for i in range(len(numbers)-1): #정렬되어있으므로 i번째와 i+1번째만 비교해보면됌
if numbers[i] in numbers[i+1]:
return False
return True
numbers=[]
t=int(input())
answer=[]
for i in range(t):
n=int(input())
for _ in range(n):
numbers.append(sys.stdin.readline().strip())
answer.append(solution(numbers))
numbers.clear()
for yn in answer:
if yn == False:
print('NO')
else:
print('YES')