Hash 고득점 kit 풀이 완료, 후기

 

Programmers 의 Hash 고득점 kit를 모두 풀이 하여 포스팅 해보았다.

Hash 함수의 정의는 입력 메시지를 고정된 길이의 출력값으로 압축 시키는 함수이다. (출처-국방과학기술용어사전)

포스팅한 Hash 문제들의 소스코드를 봤듯이, 입력된 문자열을 간단한 정수 출력값으로 변환 시켰다.

정렬같은 경우처럼 문자열들에 대한 계산이 필요할 때, 문자열을 계산할 때마다 각 문자들까지 처리해주는 것보단,

사전에 이 문자열을 나타내는 값 하나로 압축해두는 것이, 이후 계산 시 시간복잡도를 줄이는데에 매우 효과적인 것을 느꼈다.

 

해시를 이용할 때 주의할 점이 있다.

서로 다른 문자열인데도 해시값이 같을 때, 심각한 리스크가 생길 수 있다.

이를 방지하기 위해서 해시값이 같을 때에는 직접 두 입력값을 2차적으로 비교하는 처리를 해주면 된다.

프로그래머가 서로 다른 두 입력에 대해 해시값이 겹칠일이 없을 정도로 해시값을 배정 방법을 잘 정한다면, 극소의 확률로 해시값이 겹치더라도 시간복잡도를 크게 줄일 수 있는건 사실이다.

 

나의 해시값 지정 방법은 ASCII value*2^index 이었다.

문자열의 길이가 충분히 길고, 아스키 코드 값이 충분히 크다면 해시값끼리 겹칠일이 거의 없다.

앞서 포스팅한 문제들 같은 경우에는 입력 문자열이 거의 알파벳, 정수로 이루어져있었기 때문에 아스키 코드값들이 최소 48이상으로, 적당히 높은 값들을 가졌기 때문에 해시값이 겹칠일이 없었다.

그래서 직접 두 입력값을 2차적으로 비교해주는 처리를 하지 않았음에도 불구하고 모두 정답처리가 된 것이다.

중요 실무에서는 꼭 이 처리가 필요할 것이다.

 

문제 모음

[난이도 중하] 완주하지 못한 선수 kimcoder.tistory.com/81?category=886041

[난이도 중] 전화번호 목록 kimcoder.tistory.com/85?category=886041

[난이도 중] 위장 kimcoder.tistory.com/89?category=886041

[난이도 중상] 베스트 앨범 kimcoder.tistory.com/90?category=886041