23.02.14 파이썬 코딩 퀴즈#156 테이블 해시 함수 (프로그래머스 스쿨)

이번 문제는 테이블 해시 함수 이다.

해시 함수는 col, row_begin, row_end 총 3가지로 입력을 받는다.

전달받은 data를 col번째 컬럼의 값을 기준으로 오름차순 정렬하고, 만약 그 값이 동일하다면 기본키인 첫 번째 칼럼의 값을 기준으로 내림차순 정렬한다. 

이렇게 정렬화 된 데이터에서 S_i 를 i번째 튜플에 대해 각 칼럼의 값을 i로 나눈 나머지들의 합으로 정의한다.

row_brgin <= i  <= row_end 인 모든 S_i 를 누적하여 bitwise XOR 한 값을 해시 값으로 반환해야 한다.

설명 만으로는 이해가 어려우니 입출력 예를 살펴보자.

먼저 전달받은 data는 2차원 배열이다.

col 번째 (2열) 값 기준으로 오름차순 정렬하면,  {2,2,6},{4,2,9},{1,5,10},{3,8,3} 이 될 수도 있지만 S1 과 S2 의 값이 동일하기 때문에 첫 열의 값을 기준으로 다시 내림차순 하면 {4,2,9},{2,2,6},{1,5,10},{3,8,3} 순서로 정렬된다.

이때 row_begin ~ row_end 기준으로 값을 확인 하면 S_2 = (2 % 2) + (2 % 2) + (6 %2) 이므로 0이다.

마찬가지로 S_3를 계산하면 4가 되며, 따라서 해시 값 S_2 XOR S_3 는 000 xor 100 이므로 100 == 4 가 된다.

비트 연산자 XOR 은 두 수를 이진법을 변환 후 자리를 비교하여 만약 자릿수의 값이 같으면 그대로, 틀리다면 1이 된다.

 

이제 코드를 살펴보자.

용어 정리만 끝나면 특별히 어려울게 없는 문제이다.

먼저 data를 두 번 정렬해 준다. (물론 lambda x : (x[col-1], -x[0]) 이렇게 한번에 정렬하는 방법도 있다.)

이제 정렬된 데이터를 row_begin 과 row_end를 기준으로 반복하게 되는데 대상은 data[i] 가 된다.

그리고 최종적으로 만들어진 n_mod 값들을 하나씩 nums 에 넣어주면 준비는 완료된다.

이제 반복문을 이용하여 nums 를 돌며 answer ^ n 으로 비트 연산을 해주면 끝.