[python_파이썬_pass]백준_14425번_문자열 집합_풀이

공부하는허딩크 : https://www.youtube.com/live/S9Tn1JM6-yc?feature=shared

일단, 시간 제한 2초가 걸려 있어 긴장했다.

 

시간제한 조건이 있다는 건 내 마음대로 코드를 작성할 수 없고, 함수사용등에 제한이 있다.

문제는 전체적으로 이해하기 쉽게 되어 있다. 

즉 11개의 문자열이 있는데 5개의 문제열 배열과 비교해서 같은 녀석만큼 개수를 카운트 해주면 된다.

 

<첫번째 시도 : 실패>

딱히 계산을 필요로 하는 함수를 사용할 필요가 없이 for와 if를 조심스럽게 구현했다.

단, 이중for문을 사용해서 그런건지 실패했다.

import sys

input = sys.stdin.readline

#시간제한(2초) : 역시 시간초과가 뜸. 예상했음

N, M = map(int, input().split())

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

cnt = 0

for _ in range(M):

    temp = input().strip()

    for i in S:

        if temp == i:

            cnt += 1

   

print(cnt)

 

<두번째 시도 : 성공_시간이 그래도 너무 오래 걸림>

N, M = map(int, input().split())

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

cnt = 0

for _ in range(M):

    temp = input().strip()

    if temp in S:

        cnt += 1

       

print(cnt)

 

문자열 S에서 하나씩 뽑아내서 temp와 비교하는 것이 아닌 다이렉트로 temp를 S와 비교해서 cnt를 한다.

 ㄴ 처음 문제 이해를 문자열이 같은게 아닌 포함되어 있으면 cnt += 1을 하는 것으로 착각했다.

 

<다른 사람 풀이 참고>

1. list대신 set이나 dict를 사용하면 효율이 올라간다고 한다. : 이유는 해시 테이블(hash table)을 활용하기 때문

    ㄴ  어떤 임의의 단어를 숫자로 맵핑하고 이 숫자를 인덱스처럼 활용하기 때문에 속도가 빠르다.

 

확실히 list에서 찾을때(4548ms)와 dict를 활용해서 찾을때(120ms) 속도 차이가 어마어마하다.

import sys

input = sys.stdin.readline

N, M = map(int, input().split())

S = dict()

for _ in range(N):

    s = input().strip()

    S[s] = True

cnt = 0

for _ in range(M):

    temp = input().strip()

    if temp in S:

        cnt += 1

print(cnt)

 

hash함수 설명(어렵네..) : https://analytics4everything.tistory.com/180

Set, Dict의 자료구조가 검색이 빠른 이유? hash 함수