문제 링크

전화번호

문제 설명

입력으로 받은 전화번호 목록에 일관성이 있는지 검사하고, 있으면 YES를 없으면 NO를 출력한다. 이때 일관성이란, 한 번호가 다른 번호의 접두어가 되지 않는 것을 의미한다.

긴급전화: 911
상근: 97 625 999
선영: 91 12 54 26

와 같은 경우에는 긴급전화가 선영 번호의 접두어가 되므로 일관성이 없다.

문제 풀이

시도 1

처음에는 직관적으로 일일이 비교하는 방법을 사용했다. 당연히 시간초과 ,,
1. 각 테케를 길이순으로 정렬
2. 현재 번호의 길이만큼 나머지 번호를 슬라이싱하고 현재 번호와 비교

import sys

input = sys.stdin.readline

tests = []
answer = []

tc = int(input())
#각 테스트 케이스를 길이별로 정렬해서 저장
for _ in range(tc):
    num = int(input())
    tmp = []
    for num in range(num):
        tmp.append(input().strip())
    tmp.sort(key=len)
    tests.append([num, tmp])
#print(tc, tests)

for test in tests:
    n, tels = test
    flag = 0
    #print(n, tels)
    for i in range(len(tels)):
        length = len(tels[i])
        #해당 전화번호 길이만큼 슬라이싱
        for j in range(i+1, len(tels)):
            sliced_tel = tels[j][:length]
            if tels[i] == sliced_tel:
                flag = -1
                break
    if flag == -1:
        answer.append("NO")
    else:
        answer.append("YES")

for ans in answer:
    print(ans)

포문을 세개나 써서 그런지 시간초과가 났다 ㅎ_ㅎ,,

시도 2

사실 길이별로 정렬할 필요가 없는 문제였다. 그냥 사전순으로 정렬하면 prefix일 가능성이 있는 전화번호가 앞뒤로 정렬된다..

import sys

input = sys.stdin.readline

tests = []
answer = []

tc = int(input())
#각 테스트 케이스를 길이별로 정렬해서 저장
for _ in range(tc):
    num = int(input())
    tmp = []
    for num in range(num):
        tmp.append(input().strip())
    tmp.sort()
    tests.append([num, tmp])
print(tc, tests)

for test in tests:
    n, tels = test
    flag = 0
    #print(n, tels)
    for i in range(len(tels)-1):
        if tels[i] == tels[i+1][:len(tels[i])]:
            flag = -1
            break
    if flag == -1:
        answer.append("NO")
    else:
        answer.append("YES")

for ans in answer:
    print(ans)

때로는 간단하게 생각해보긔

시도 3 - startwith함수 사용

스터디하면서 다른 분 풀이를 봤는데 startwith 함수를 사용하셔서 다시 풀어보았다.