[실버 1] 백준 1141 - 접두사 (파이썬)

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

풀이

이 문제는 주어진 문자열들 중 다른 문자열의 접두사가 아닌 문자열의 개수를 세는 것이다.

N = int(input())
S = [input() for _ in range(N)]
S = list(set(S))  # 중복 제거

먼저 문자열 개수 N을 입력받고, 문자열 리스트 S를 구성한 뒤 set()을 이용해 중복 문자열을 제거한다.

prefix = [False] * N

prefix[i]는 S[i]가 다른 문자열의 접두사인지 여부를 저장하는 배열이다.

for i in range(len(S)) :
    for j in range(len(S)) :
        if i == j : 
            continue
        if len(S[i]) >= len(S[j]) :
            continue
        if S[i] == S[j][:len(S[i])] :
            prefix[i] = True
            break

두 문자열을 비교하여, S[i]가 S[j]의 접두사인지 확인한다.

단 조건은 다음과 같다.

1. 같은 인덱스는 패스한다.
2. 자기보다 길거나 같은 문자열은 확인하지 않는다.
3. 접두사인지 확인은 S[i] == S[j][:len(S)]로 한다.

접두사로 확인되면 prefix[i] = True로 설정하고 바로 break 한다.

count = 0
for i in range(len(S)) :
    if not prefix[i] :
        count += 1

접두사가 아닌 문자열 개수를 카운트한다.

코드

# 백준 1141 - 접두사
# 분류 : 문자열

N = int(input())
S = [input() for _ in range(N)]
S = list(set(S))

prefix = [False] * N

for i in range(len(S)) :
    for j in range(len(S)) :
        if i == j : 
            continue

        if len(S[i]) >= len(S[j]) :
            continue

        if S[i] == S[j][:len(S[i])] :
            prefix[i] = True
            break

count = 0
for i in range(len(S)) :
    if not prefix[i] :
        count += 1

print(count)