해시알고리즘 두번째 문제 전화번호 목록이다.

문제 이해

문제를 보면 전화번호부를 리스트 형식으로 주는데 첫번째 예를 보면 ["119", "97674223", "119552421"] 이렇게 나와있는걸 볼수 있다 여기서 어떤 한 번호가 다른 사람의 번호의 접두어 즉 시작점을 알리는 문자인지를 확인하는 문제라고 볼수가 있다.

이전에 해시알고리즘에 대해서 어느정도 알고 시작하게 됬으니 바로 해시알고리즘을 사용해서 문제를 해결해 보도록 하겠습니다.

문제 해결

일단 접근을 할때 접두어라고 한다고 하면 어떤 번호가 다른 어떤 번호의 시작점부터 몇번째 문자까지의 값과 동일해야 한다고 생각을 할수가 있습니다. 그럼 일단 hash_table이라는 dict에 각번호마다 가지고 있는 hash값을 key값 그 번호를 value값으로 넣어주게 됩니다.

그렇게 되면 이런식으로 dict가 나오게 되고 그다음에 이제 번호를 비교를 해볼수가 있는데 for문으로 다시 리스트를 출력해주고 그 번호마다 다시 한글자씩 쪼갠후에 공백문자열로 변수를 지정해준 number_string값에다가 하나씩 넣어주면서 그 해시값이 들어있는 key값이 존재하는 확인해 주면 됩니다. 여기서 중요한거는 예를 들어 "119"를 돌려서 "119"라는 key와 비교를 하면 당연히 똑같은 값이 나오기 때문에 이것은 건너 뛰어야 한다는 걸로 and number_string(비교할 문자) number(조회하는 문자)와 똑같다면 확인하지 않는다고 해주어야 값이 나오게 됩니다.

문제 풀고 나서

다른 사람들 문제 풀이를 보면 startswith()라는 메소드를 사용해서 비교하는 방법도 있고, hash값을 따로 구하지 않고도 그 값을 비교한 경우도 있는것을 확인할수 있었습니다. 문제를 풀수록 좀더 효율적인 방법을 모색할수 있다고 생각하니 흥미롭다고 느낄수가 있었습니다.