[파이썬, Python] 백준 14425 : 문자열

백준 14425 번 : 문자열 집합

📖 문제 📖

 

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

 

---

📺 입력&출력 📺

---

📝 풀이 📝

M개의 문자열을 N개의 집합에 하나하나 비교를 하며 같은 값이 있으면 결과 값을 1씩 더해주는 방법을 생각했습니다.

 

문자열 개수 n과 m이 각각 최대 10,000개 씩이라고 한다면 연산은 최대 1억번이기 때문에 가능할 수도 있겠다고 생각했습니다.

---

👨‍💻 나의 코드 👨‍💻

import sys
n,m = map(int,sys.stdin.readline().split())
list_s = []
for _ in range(n):
    list_s.append(sys.stdin.readline())
result = 0
for _ in range(m):
    if sys.stdin.readline() in list_s:
        result+=1
print(result)

 

---

👩‍👩‍👧‍👧 다른 사람의 코드 👩‍👩‍👧‍👧

import sys
n,m = map(int,sys.stdin.readline().split())
set_s = {}
for _ in range(n):
    set_s[sys.stdin.readline()] = True
result = 0
for _ in range(m):
    if sys.stdin.readline() in set_s:
        result+=1
print(result)

다른 사람들의 코드를 보니 대부분 set을 쓴 것을 볼 수 있었습니다.

이유는 List보다 더 빠르기 때문이라고 합니다.

---

List와 Set의 탐색 속도 차이

두 방식 모두 안에 요소가 포함되어 있는지 여부를 알 수 있는 in연산자를 사용할 수 있습니다.

여기서 같은 in이라도 Set의 속도가 더 빠릅니다.

 

List는 in 연산자를 사용하면 for문을 한번 도는 것( O(n) )과 같습니다. 

하지만, Set은 in 연산자를 사용시 복잡도가 O(1)입니다.

Dictionary 키를 탐색하는 in 역시 set과 동일한 시간 복잡도 O(1)를 가집니다.

---

정리

List의 in - O(n)
Set의 in - O(1)
Dictionary의 in - O(1)
웬만하면 탐색을 할 때 가능하다면 List보단 Set이나 Dictionary를 사용하는 것이
속도를 높이는데에 더욱 도움이 될듯합니다.

다음과 같이 List를 set으로 바꾸어 주기만 했더니 시간이 월등히 빨라진 것을 확인 할 수 있었습니다.