[python] 백준 14425 - 문자열 집합

📍 백준 14425 - 문자열 집합

문제: 백준 14425 - 문자열 집합

💡 나의 풀이

저번에 풀었던 듣보잡 문제와 비슷한데, 시간복잡도를 추가적으로 고려해야하는 문제였다.
입력조건에 N과 M이 (1<= N,M <= 10,000)으로 주어졌는데,

기본적으로 input()을 sys로 선언한다고 해서 해결되는 문제가 아니었다.
그래서 처음에 선언했던 count가 문제인줄 알고 if ~ in ~으로도 해봤지만 결과는 똑같았다.

찾아보니 파이썬의 자료형에 따라 시간복잡도가 다른데 그것을 생각하지 못했다.
일반적으로 list의 삽입, 제거, 탐색, 포함여부는 보통 시간복잡도가 O(N)이고
dict, set의 삽입, 제거, 탐색, 포함여부는 보통 시간복잡도가 O(1)이다.

dict, set의 시간복잡도가 낮은 이유는 hash값을 사용하기때문에 빠른 접근이 가능하다.

값의 순서, index에 접근할때는 보통 list를 많이 사용하고, 값의 탐색이나 확인은 보통 dictionary, set형을 많이 사용한다.

사진 하단의 시간복잡도가 높게 나온 판정은 list형으로, 상단의 시간복잡도가 낮게 나온 판정은 dictionary, set형을 이용했을 때의 사진이다.

확연하게 차이가 나는것을 확인할 수 있다.

⚡️ 결론

정답판정을 받았는데 시간복잡도가 너무 높게나온다 싶으면 자료형을 바꿔서 적용해보자!!!

# 방법 1: dict()
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
cnt = 0
S = dict()

for i in range(n):
    index = input().strip()
    S[index] = True

for j in range(m):
    check = input().strip()
    if check in S:
        cnt+=1
print(cnt)

# 방법 2: set()
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
cnt = 0

S = {input().strip() for _ in range(n)}

for j in range(m):
    if input().strip() in S:cnt+=1
print(cnt)

# 잘못된 방법 3: list()
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
cnt = 0

S = [input().strip() for _ in range(n)]

for j in range(m):
    if input().strip() in S:cnt+=1
print(cnt)