[파이썬] 백준 14425번 「문자열 집합」

문제

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

14425번: 문자열 집합

 

 

문제 분석

n과 m 을 입력받고 n개의 문자열이 들어있는 s집합에 m개의 다른 문자열들이 몇 개가 포함되어있는가(일치하는가)를 찾는 문제이다.

주의 해야할 점은 N의 범위는 최대 10000개, M의 범위도 최대 10000개 이므로, 둘 다 반복성이 있는 리스트 또는 튜플을 이용하게 된다면 M의 마지막 단어가 N에 포함되어 있지 않은 경우 이미 10000번째 까지 반복되어 왔는데, N을 10000번 더 돌려야하기 때문에 제한시간 2초내에 해당 문제를 풀기에는 시간초과가 발생할 것이다. 

 

 

 

풀이 전략

앞서 말했듯, 이중for문을 이용하게 되면 최악의 경우 10000*10000의 반복을 하기에 시간초과가 발생할 것이므로, 반복을 줄여야한다. 문자열 s의 경우에는 반복성이 없는 set() 집합을 이용하거나 딕셔너리 dict()를 사용하면 해당 집합 안에 어떠한 요소가 들어있는지 확인하는 시간복잡도는 O(1)이므로 시간을 굉장히 단축시킬 수 있다.

그러므로 n개의 요소를 가진 집합 s를 생성하고, m개의 단어들을 돌면서 입력받은 단어가 집합 s에 존재하는지 확인하여 존재하면 개수를 세기만 해주면 된다.

본인은 집합 set()을 이용하여 문제를 해결하였다.

 

 

 

 

코드

 

 

 

 

 

결과

 

 

고찰

처음에 풀었을 때는 집합 s에 ABCDE가 있고, ABC가 s에 존재하는지 확인했을 때 부분문자열도 개수에 포함되는 것으로 판단하여 이중for문으로 돌려서 확인하였는데 시간초과가 발생하였다. 그래서 문제 해석이 굉장히 중요하였다. 결국 그냥 일치하는 지만 확인하면 되는 문제였으므로 굉장히 간단하게 문제가 해결되었다.

set 함수의 시간복잡도는 O(1)이고, 집합과 집합, 순회 등에서는 해당 집합의 길이만큼(예외 존재) O(len(s)) 라는 것을 기억해두자. 굉장히 빠르게 어떤 요소가 존재하는지 파악할 수 있다.