백준 1141 접두사 (파이썬)

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

1141번: 접두사

 

n이 50이므로 이중 for문으로 풀면 쉽게 풀 수 있는 문제입니다. (50 * 50 < 10^9)

먼저 주어진 문자열들을 길이 순으로 정렬합니다.

길이가 긴 문자열은 길이가 짧은 문자열의 접두사가 될 수 없다는 특징을 이용하여

비교할 문자열의 다음 index부터 접두사인지 검사하면 됩니다.

 

 

n = int(input())
lst = []
for _ in range(n):
    lst.append(input())
lst.sort(key=lambda x: len(x))
res = 0
for i in range(n):
    chk = True
    for j in range(i + 1, n):
        if lst[j].startswith(lst[i]):
            chk = False
            break
    if chk:
        res += 1
print(res)