[백준][Python] 1141 접두사

그리디, 문자열, 정렬 / 실버 1

🐉

 

https://www.acmicpc.net/problem/1141

1141번: 접두사

 

내 풀이

N = int(input())
words = []
ans = 0

for _ in range(N):
    words.append(input())

for i in range(N):
    for j in range(N):
        if i == j:
            continue
        if words[j].find(words[i]) == 0: # 0일 때 접두사
            words[i] = ""
        
for j in words:
    if j != "":
        ans += 1

print(ans)

 

모든 단어를 돌면서 어떤 단어의 접두사가 될 수 있는 단어라면 ""로 임의 삭제 처리했다.

find 함수를 사용해서 0인 경우에 접두사가 될 수 있는 단어로 간주했다.

(실제로 삭제(remove)하면 for 문에서 범위 에러가 발생하여 빈 문자열로 치환함)

 

모든 단어 검사 후, words에서 ""(빈 문자열)이 아닌 단어의 개수가 접두사X 집합인 부분 집합의 최대 크기가 된다.

 

 

수정 (정렬 사용)

N = int(input())
words = []
ans = 0

for _ in range(N):
    words.append(input())

words.sort(key=len)

for i in range(N):
    for j in range(i+1, N):
        if words[j].find(words[i]) == 0: # 0일 때 접두사
            words[i] = ""
        
for j in words:
    if j != "":
        ans += 1

print(ans)

 

 

처음 푼 풀이에서는 문자열의 길이와 상관없이 모든 문자열을 검사하였는데,

어떤 단어가 다른 단어의 접두사가 되기 위해서는, 해당 단어의 길이와 같거나 짧을 수밖에 없다.

 

따라서, 먼저 문자열의 길이대로 오름차순 정렬 후, 검사할 때 그 다음 위치부터 검사하는 것이 더 효율적이다.

 

# 처음 알게 된 문법
# 문자열의 길이를 기준으로 정렬

words.sort(key=len) 

 

 

시간 차이는 딱히 없었다!