백준/ Silver 2 문제 , 백준 파이썬 1141 , 접두사 , 정렬

백준/ Silver 2 문제 , 백준 파이썬 1141 , 접두사 , 정렬

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
푸는데 1시간 정도 걸렸다. 문제를 잘못이해해서 최대한 쪼개는걸로 풀었는데, 알고보니 최대한 모으는거였다.

 

<문제 출처>

 

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

1141번: 접두사

 

 

 

 

------------------------------------------------------------------------------------------------------------------------------

 

ex1)

6
hello
hi
h
run
rerun
running

 

 

정리한 store 리스트 출력.

 

 

 

sort로 정렬해준 뒤 뒤에 단어와 비교해준다.

 

(뒤에 단어랑 비교하는 식으로 이어나아가기 때문에 반드시 해줘야한다.)

 

 

만약 접두어 부분에 해당하게되면 뒤에 단어를 앞의 단어와 같은 집합에 추가한다.

 

그 다음 for 문을 돌면 앞의 단어와 뒤의 단어가 서로 접두어 관계가 아니다.

 

이 경우 새로운 집합을 만들어 저장한다.

 

이런 식으로 만들면 크게 부분집합이 4개 나오게 되는데

 

각 부분 집합에서 원소를  하나씩 뽑아 조합하면 부분집합의 갯수와 같은 같이 최대 크기가 4개인 집합이 형성된다.

 

ex) [ hello, hi, rerun, running]

 

 

참고로 h 는 hi 와 접두어 관계라 h 를 뽑아서는 안된다.

 

어차피 이런식으로 분류를 하게되면 각 부분집합에 뽑을만한 원소가 무조건 하나씩은 들어있다.

 

 

 

ex2)

 

6
a
ab
abc
abcd
abcde
abcdef

 

 

 

 

예제 2번의 경우 모두 각 단어의 앞자리와 접두어 관계이기때문에

 

한개의 집합만 형성되어있다.

 

이 집합에서 하나를 뽑을수 밖에 없으니 답은 한개이다.

 

 

 

 

 

ex3)

 

3
topcoder
topcoder
topcoding

 

 

 

 

 

예제 3번의 경우 부분집합이 두개 형성되었다.

 

이중에 한개씩 뽑아써야하니 답은 두개이다.

 

 

 

 

 

결국, 답은 store에 저장되는 부분집합의 갯수와 같기 때문에 부분집합이 하나씩 늘어날때마다

 

result+=1 을 통해 생성된 부분집합의 갯수를 카운트해줬다.

 

이후 출력은 이 result 변수값만 해주면 된다.

 

 

 

 

 

 

------------------------------------------------------------------------------------------------------------------------------

정답

 

 

 

 

 

 

import sys
input=sys.stdin.readline

N=int(input())
words=[input().rstrip('\n') for _ in range(N)]
words.sort()
store=[[]for _ in range(N)]
store[0]=[words[0]]
result=1
cnt=0

for i in range(1,N):
    if words[i-1]==words[i][0:len(words[i-1])]:
        store[cnt].append(words[i])
    else:
        cnt+=1
        store[cnt].append(words[i])
        result+=1

print(result)