[伯俊/141]接頭辞

3760 ワード
白駿 テキストリンク

1.質問する


接頭辞X集合は、集合内のある語であり、別の語の接頭辞の集合ではない.たとえば,{hello},{hello,goodbye,game,hi},空の集合はいずれも接頭辞X集合である.しかし,{hello,hell},{giant,gig,g}は接頭辞X集合ではない.
N個の単語からなる集合を与える場合、接頭辞Xの部分集合の最大サイズを出力します.

2.入力


1行目は単語の個数Nを与える.Nは50以下の自然数である.2行目からN行に単語があります.単語は小文字のみで構成され、最大長は50です.集合中に同じ語を2回以上持つことができる.

3.コード

import sys
sys.stdin = open('input.txt')

n = int(input())
lst = [input() for _ in range(n)]
lst.sort() # 정렬하면 시간이 더 줄겠죠?
excep = lst[:] # 접두사인 단어는 삭제할 예정

for idx, test in enumerate(lst):
    for temp in lst[idx:]: # test접두사인가? / 비교대상 temp
        # test랑 temp가 동일한 애일때 검사 안함(test != temp)
        # 근데 본인아닌데 동일한 애도 검사를 피해가기때문에 밑에서 set해준다.) 
		# 비교대상 temp를 test접두사길이까지 잘라서 비교해보고 같으면 제거
        if test != temp and test == temp[:len(test)]: 
            excep.remove(test)
            break
            
# 동일한 단어는 제거
print(len(set(excep)))
Nest
rails generate が全然動かない！時に試すこと