[백준] 문자열 집합(14425번) - Python

✅문제 - 문자열 집합(14425번)

---

✅오늘 배운점

---

문제에서 두 집합 간의 비교를 위해 in method를 사용하였다.

하지만 처음에 list에서 in method를 사용한 경우에 시간이 3724ms나 소요 되어 문제가 있다고 판단했다.

그래서 list를 set로 변경하였더니 시간이 116ms로 감소하였다.

이유는 파이썬 홈페이지에서 확인할 수 있었다

set 자료형에서 in method의 시간복잡도는 최선: O(1) 최악: O(N)이고

list 자료형에서 in method의 시간복잡도는 O(N)인 것을 확인할 수 있었다.

 

 

 

❗❗❗ 앞으로 성분의 포함 여부를 사용할 때는 set를 사용하자!!

 

✅첫 코드 - (시간 3724ms)

---

import sys

index = int(sys.stdin.readline().rstrip().split()[0])

word_list = sys.stdin.readlines()
checks = word_list[:index]
words = word_list[index:]

count= 0

for word in words:
    if word in checks:
        count+=1

print(count)

 

해설

words의 성분이 checks에 있는 경우 count 값을 1 올리고 그 값을 출력하였다.

 

❗❗❗시간  초과 발생 이유 ( .in() method ) 

list에서 in method를 사용하면 시간 복잡도가 O(N)이기 때문에 총 시간 복잡도가 O(N^2)이 된다.

 

 

✅개선 코드 - (시간 116ms)

---

import sys

index = int(sys.stdin.readline().rstrip().split()[0])

word_list = sys.stdin.readlines()

#이 부분을 list에서 set로 바꿔준다!!!
checks = set(word_list[:index])

words = word_list[index:]

count= 0

for word in words:
    if word in checks:
        count+=1

print(count)

 

해설

checks 를 list가 아닌 set로 바꿔주면 in method를 사용할 때 시간복잡도가 O(1)로 줄어든다 !!