프로그래머스에서 코딩테스트 고득점 Kit문제에서 해시 문제를 풀어보려고 한다.

완주하지 못한 선수

일단 문제를 이해해 보면 마라톤 참가를 한 선수들이 있는데 한명의 선수만 완주를 못했다. 거기에서 그 사람을 찾아라 라는 문제라고 이해를 했다.
처음 문제를 접했을때는 해시알고리즘을 생각 하지 않고 단순하게 풀면 앞에 participant에서 뒤에 completion이부분을 빼면 되는거 아닌가? 라고 생각하고 문제를 접근했다.

요렇게 하면 participant리스트에서 completion에 있는 원소들을 빼주면 결국 남은 사람은 한사람만 남으니 답이겠구나 하고 결과를 봤는데

아... 답은 맞는데 효율성이 떨어진다.. 시간복잡도가 낮다라는 뜻인것 같았다..

그럼 두번째 방법

participant리스트와 completion리스트를 sort를 해서 비교하는 방법이다. completion의 배열의 길이만큼 index를 서로 비교를 한다를 방법인데

이런식으로 sorting이 되었을때 0번째 index부터 completion의 마지막 index까지 비교해서 다른값이 나오면 participnat에 해당 index를 뽑아내고 그냥 for문이 끝났을때는 결국 participant의 마지막 index사람이 완주를 못해다고 결과가 나오니 paritipant[i+1]을 해주면 결과가 나오는것을 확인할수 있다.

결과를 돌려보면 해결이 되었다고 볼수가 있는데.. 여기서 중요한건 이건 단순히 sort를 통해서 문제를 해결한것일 뿐이지 해시 알고리즘을 사용했다고 볼수가 없다...
그래서 해시 구조를 좀 알아볼 필요가 있는데

해시 구조

키(KEY) 값(VALUE) 쌍으로 이루어진 데이터 구조 이때 KEY를 이용해서 데이터를 찾아 속도가 빠르게 찾을수 있는 구조를 가지고 있다.

풀이 방법은 hash_table이라는 dict와 hash_sum가 0이라는 변수를 만듭니다. 그리고 paritipant에 문자들의 hash값을 hash_table에 넣습니다. 그러면서 나온 hash값들의 합을 구하게 되고, 그후 completion의 문자들의 hash값을 이제 hash_sum이라는 값에서 빼주게 되면 어떤 특정 문자의 hash값이 나오게 되는데 이 값이 서로 중복되지 않은 하나의 값이 되기 때문에 hash_table에서 key값을 마지막에 나온 hash_sum을 넣어 주게 되면 그 문자가 출력이 되게 된다고 보면 됩니다.

확실히 일반 sort로 문제를 해결할때보다 hash방식으로 문제를 해결하니깐 시간차이가 1.5배에서 두배정도 차이가 나는것을 확인할수가 있었습니다. 프로그램에서 0.000x 초 싸움이 크다고 생각해보면 이래서 알고리즘을 사용해야 한다고 느끼는 문제 같습니다.