해시 함수는 해시 충돌을 최대한 줄이기 위해 사용합니다.
두 번째 해시 함수는 해시 충돌이 쉽게 일어나는 방식이라 시간 초과가 발생한 것으로 보입니다.
간단한 예시로, 두 번째 해시 함수에서 "hi"라는 문자열은 문자열 ap, bo, cn, dm, el, fk, gj, ih, jg, kf, le, md, nc, ob, pa와 해시 충돌이 발생합니다.
두 글자로 된 문자열이라 예시가 많진 않은데, 아무튼 어렵지 않게 해시 충돌이 일어나는 해시 함수임을 알 수 있습니다.
그럼 해시 충돌을 줄이기 위해서는 어떻게 하냐... 최선책은 정답 코드의 해시 함수처럼 잘 만들어진 해시 함수를 사용하는 겁니다.
하지만 위 코드는 조금 복잡하기도 하고, 알고리즘 문제의 목적은 테스트 케이스 통과이므로 그렇게 정교한 해시 함수를 만들 필요는 없습니다.
즉, 적당히 잘 만들어진 해시 함수면 충분합니다.
해시함수를 적당히 잘 만드는 방법은 정답코드의 해시 함수 처럼 결과값에 매번 적당히 큰 소수(65599)를 곱해주는 겁니다.
실제로 hemisphere1357님의 해시 함수를 제가 작성한 코드처럼 적당히 바꾸기만 해도(1231은 소수입니다) 쉽게 통과할 수 있습니다.
해시 함수 외에 도움이 되는 방법이라면 해시 테이블을 예상되는 전체 개수의 2배 정도로 크게 잡는 겁니다.
해시 함수를 만드는 이유가 해시 충돌을 줄이기 위해서니까, 애초에 테이블 크기를 크게 잡아 충돌이 날 확률을 줄이면 시간 초과를 피할 수 있습니다.
이번 문제의 경우는 200000개 정도의 배열을 해시 테이블로 잡는 것을 추천합니다.
그리고 마지막으로 C언어의 strlen 함수는 문자열 길이를 알기 위해 문자열을 한번 순회합니다.
for문 안에 선언하게 되면 for문의 조건문을 검사할 때마다 strlen 함수를 실행시키게 되므로, for 문 바깥에 문자열 길이를 따로 구해놓고 for 문의 조건문에서는 따로 구해놓은 값을 사용하면 좋을 것 같습니다.

hemisphere1357 1년 전 1
안녕하세요.
멍청한 질문일 수 있지만 질문을 작성해봅니다.
아래 소스 코드는 해시 함수 두 개를 나타냅니다.
첫 번째 해시 함수를 사용해서 답을 맞췄는데, 책에서 가지고 온 함수에요.
두 번째 해시 함수는 수업에서 배웠던 건데, 이걸 사용했더니 아주 근소한 차이로 시간 초과가 났습니다.
아마 두 번째 해시 함수가 충돌 빈도가 높았던 걸로 생각되는데, 해시 함수를 바꿨다고 정답을 맞춘 게 사실은 찝찝해요.
두 번째 해시 함수에는 무슨 문제가 있었던 걸까요?
그리고 혹시 몰라서 제 정답 코드 아래에 남겨둡니다.
이 코드에서 시간을 더 아낄 수 있는 부분이 있는지 궁금합니다.
https://www.acmicpc.net/source...
감사합니다.