rjs463   2년 전

시간초과가 나오는 이유를 아무리 생각해도 찾을 수가 없습니다. 살려주세요.. 절실합니다.

해쉬로 풀고자 하였습니다. 포켓몬 이름을 해쉬함수로 돌려서 해쉬 테이블에 넣었고, 이름에 해당하는 번호를 저장하는 배열을 만들어 약간은 가라로 짰긴 했습니다만 시간 초과가 왜 나오는지 아무리봐도 이해가 되지 않습니다. 고수님들 도와주세요..

djm03178   2년 전

해시 함수가 해시의 역할을 적절히 하지 못하고 있습니다.

61번째 줄에 보면 마지막에 & MAX_SIZE를 하는데, 이 때문에 hash가 가질 수 있는 값은 MAX_SIZE를 이진수로 표현했을 때 1인 자릿수의 개수에 따라 결정됩니다. 1000001은 이진수로 11110100001001000001, 즉 1이 8개이기 때문에 2^8=256가지 값밖에 나타내지 못하고, 이 때문에 서로 다른 이름끼리 key가 겹치는 일이 매우 많아지게 됩니다. 그래서 탐색에 매우 오랜 시간이 걸립니다.

& MAX_SIZE만 지우면 맞습니다.

jh05013   2년 전

% MAX_SIZE를 의도하셨나 보군요.

댓글을 작성하려면 로그인해야 합니다.