[BOJ 1141] 접두사

1141번: 접두사

문자열들을 정렬해서 해결할 수 있는 문제이다.

단어 A가 단어 B의 접두사가 되려면 반드시 B의 길이가 A의 길이 이상임을 이용한다.

 

1. 입력받은 단어를 길이가 짧은 순으로 정렬한 다음,

2. 모든 단어를 확인한다. 한 단어를 확인할 때엔 그보다 길이가 같거나 긴 모든 단어를 확인한다.

3. 자신보다 길이가 같거나 긴 단어에 대해 확인 중인 단어가 접두사가 아니라면,

    그 단어는 접두사X 집합에 들어갈 수 있으니 ans 변수의 값에 1을 더해 집합 원소의 개수를 갱신한다.

 

In = __import__('sys').stdin.readline
N = int(In().rstrip())
words = []
for _ in range(N):
    temp = In().rstrip()
    temp_len = len(temp)
    words.append((temp, temp_len))

words.sort(key=lambda x: (x[1]))
ans = 0
for i in range(N):
    temp = words[i][0]
    flag = 0
    for j in range(i+1, N):
        if temp == words[j][0][:words[i][1]]: 
            flag = 1
            break
    if not flag: ans += 1

print(ans)