1141번: 접두사 (acmicpc.net)

##
그리디 알고리즘, 문자열, 정렬 문제



## code
import sys
input = sys.stdin.readlines
l = list(map(lambda x:x.rstrip().replace('\x1a',''), input()[1:]))

# 단어가 길수록 접두어가 될 가능성은 낮다
# 긴것부터 고르고, 만약 이미 선택된것의 접두어라면 제외한다
l.sort(key=len,reverse=True)

words = []

def is_front(words,n):
    for tmp in words:
        if tmp[:len(n)] == n:
            return True
    return False

words.append(l[0])
for tmp in l[1:]:
    if is_front(words,tmp):
        continue
    else:
        words.append(tmp)
print(len(words))

단어가 길면 접두어가 될 가능성이 낮으니까. 긴 단어부터 넣고, 짧은 단어를 넣으면 접두사 X 집합이 되는지 확인하면서 추가한다.