[백준 BOJ_1141] 접두사 Python 풀이

출처: 백준 온라인 저지

문제

풀이

접두사가 아닌 문자열을 찾기 위해 다른 단어의 접두사인 단어의 수를 세어주기로 했습니다.

우선 같은 문자열이 있다면 하나만 포함할 수 있으므로 중복을 제거해주기 위해 set을 썼습니다.

그런 뒤 보다 빠르게 접두사를 찾아주기 위해 정렬을 해주었습니다. 만약 아래와 같이 list가 있다면 h는 다른 단어들의 접두사이므로 제일 먼저 나와주어야 더 빠르게 제외시킬 수 있습니다.

["h", "hi", "hello"]

이중 for loop을 돌며 각각의 단어의 길이만큼 다른 단어를 slicing하여 같은지 비교하며 접두사인지 아닌지를 판단하였습니다.

• words를 오름차순으로 정렬해주었기 때문에, 길이가 같거나 짧은 단어는 자신보다 앞쪽에 옵니다.
• 길이가 같다면 아예 단어가 같아야 하기 때문에 앞서 중복으로 제거해주었기 때문에 확인해주지 않아도 됩니다.
• 길이가 짧다면 현재 단어는 자신보다 짧은 단어의 접두사가 될 수 없기 때문에 j는 i부터 돌아줍니다.

만약 접두사라면 cnt를 늘려주고 바로 break를 해주었습니다. 이미 다른 단어의 접두사임을 확인한 단어를 또 다른단어들과 비교해줄 필요가 없기 때문입니다.

마지막에는 중복을 제외한 words의 길이에서 접두사의 개수인 cnt를 빼주었습니다.

코드

N = int(input())
words = sorted({ input() for _ in range(N) })
cnt = 0
for i in range(len(words)):
    for j in range(i+1, len(words)):
        if words[j][:len(words[i])] == words[i]:
            cnt += 1
            break

print(len(words)-cnt)