[python_파이썬_pass]백준_14425번_문자열 집합_풀이
공부하는허딩크 : https://www.youtube.com/live/S9Tn1JM6-yc?feature=shared
일단, 시간 제한 2초가 걸려 있어 긴장했다.
시간제한 조건이 있다는 건 내 마음대로 코드를 작성할 수 없고, 함수사용등에 제한이 있다.
문제는 전체적으로 이해하기 쉽게 되어 있다.
즉 11개의 문자열이 있는데 5개의 문제열 배열과 비교해서 같은 녀석만큼 개수를 카운트 해주면 된다.
<첫번째 시도 : 실패>
딱히 계산을 필요로 하는 함수를 사용할 필요가 없이 for와 if를 조심스럽게 구현했다.
단, 이중for문을 사용해서 그런건지 실패했다.
<두번째 시도 : 성공_시간이 그래도 너무 오래 걸림>
문자열 S에서 하나씩 뽑아내서 temp와 비교하는 것이 아닌 다이렉트로 temp를 S와 비교해서 cnt를 한다.
ㄴ 처음 문제 이해를 문자열이 같은게 아닌 포함되어 있으면 cnt += 1을 하는 것으로 착각했다.
<다른 사람 풀이 참고>
1. list대신 set이나 dict를 사용하면 효율이 올라간다고 한다. : 이유는 해시 테이블(hash table)을 활용하기 때문
ㄴ 어떤 임의의 단어를 숫자로 맵핑하고 이 숫자를 인덱스처럼 활용하기 때문에 속도가 빠르다.
확실히 list에서 찾을때(4548ms)와 dict를 활용해서 찾을때(120ms) 속도 차이가 어마어마하다.
hash함수 설명(어렵네..) : https://analytics4everything.tistory.com/180
Set, Dict의 자료구조가 검색이 빠른 이유? hash 함수
Summary: set, dict은 해시함수를 이용한 해시값을 저장하고있는 해시테이블이란 자료구조를 사용하기 때문에, 빠른 탐색이 가능함. 해시는 임의의 변수(문자열 등)를 숫자로 변환하여, 매핑하는 것
analytics4everything.tistory.com