[백준/python] 1141번 접두사

1. 문제

 

이 문제는 접두사X집합의 최대 크기를 구하는 문제이다.

주어진 배열에서 어떤 단어가 다른 단어의 접두어가 되지 않는 부분집합을 만들어야 한다.

단어의 개수는 최대 50이어서 숫자가 크지 않다.

 

2. 풀이

접두어가 되려면 자신보다 길거나 같은 길이의 문자여야 하므로

길이를 기준으로 짧은 길이부터 긴 길이 순으로 정렬을 했다.

이후 이중 반복문을 사용하여 가장 짧은 단어부터 시작해 자기 자신 다음 단어부터 가장 긴 단어까지 확인한다.

만약 단어 j를 i 단어의 길이 만큼 잘라서 i와 자른 j가 같다면 단어 i는 부분집합에 들어갈 수 없다.

 

직접 배열 자체에서 그 단어를 삭제하는 것도 방법이지만,

결국 출력해야 하는 것은 크기 값 뿐이므로 ans 변수를 새로 만들어 겹치는 단어를 빼주었다.

처음에는 n 자체를 변경하였으나 이중 반복문 범위에 n을 사용해서 이 값을 변경하면 문제가 생긴다.

따라서 새로운 변수를 만들어 두 단어가 같을 때마다 1씩 빼준 뒤 출력했다.

 

3. 코드

n = int(input())
#배열 입력 받아서 길이에 따라 정렬하기
arr = sorted([input() for _ in range(n)], key=len)
ans = n #ans 초기화 (n을 바로 변화시키면 반복문에 문제가 생김)

#반복문을 실행하여 arr[i]와 같은 길이만큼 자른 arr[j] 값이 같을 경우 ans에서 1 빼기
for i in range(n):
    for j in range(i+1, n):
        if arr[i] == arr[j][:len(arr[i])]:
            ans -= 1
            break
print(ans)

4. 결과

매우 수월하게 해결했다!

특정 알고리즘을 생각하느라 힘들었던 최근 문제들과 달리 그리디는 편안...