프로그래머스 js, cpp, python3 - level1 체크했을 때, 가장 먼저 뜬 문제다.
https://programmers.co.kr/learn/courses/30/lessons/42576
-
thinking flow
N, N-1 input array 가 존재한다. 일단 무조건 한번씩은 참조를 해야 한다고 생각 -> 최소 O(2N)
비교를 해야 되는데 단순 brute force 비교면 O(N^2) -> 비효율 최대
비교를 줄이는 방법??? 사이트에서 키워드로 '해시' 가 달려있다... (생각이 제한된다.. ㅠ)
string 을 일대일 매칭되는 숫자로 바꿔서 비교??
참가자 배열 element 각각 해시값의 합에서 완주자 배열 element 각각 해시값의 합을 빼면 남는 숫자 값은 완주하지 못한 참가자의 값이 된다. 다시 역으로 string 으로 바꿔주면 끝
--> O(N) 알고리즘 완성
그럼 해시 알고리즘은 어떻게??
알파벳은 26개, a=1,b=2 ... z=24 에 자릿수마다 *100 하면 간단
근데 길이가 20 인 참가자 이름도 있는데? 딱봐도 숫자가 정수형 최대값 넘을 것 같네;;
그냥 숫자합을 20개로 해서 빼자.
첫째 자리 합, 둘째 자리 합 ... 20째 자리 합 비교 ㄱㄱ -
결과
https://github.com/songjy6565/alg-js/blob/master/programmers/A1.js
hash function 을 멍청하게 만들다 보니 javascript 코드가 300줄가까이 나왔다 ㅋㅋ
cpp과 python 까지 하기엔 심한 단순 작업이 될 것 같아 이번엔 패스하겠다.
from string to int (vice versa) hash function을 구글링 해보았지만 encryption 내용들만 널려 있어서 따로 reference 를 기록해두진 않음. (보안쪽도 배웠는데 hash 하나 영리하게 못짜겠네.. ㅠ)
