python 1141번 접두사 (백준)

n = int(input())
a=[]
for _ in range(n):
    s = input()
    a.append(s)
a.sort()

i=0
while i<len(a):
    e=len(a[i])
    j=i+1
    while j<len(a):
        if a[i]==a[j][0:e]:
            a.pop(i)
            i-=1
            break
        j+=1
    i+=1
    
print(len(a))

 

풀이 : 정렬

 

1. 알파벳 오름차순 기준으로 리스트에 문자열을 넣어놓은 것을 정렬한다.

2. 순차적으로 탐색하며 만약 자기 자신이 다른 문자열의 접두사가 될 수 있다면 이 문자열은 리스트에서 삭제한다.

3. 위의 과정을 반복하다보면 모든 문자열을 탐색하게 된다.

4. 리스트에 남아있는 문자열들의 개수가 정답이다.