코딩테스트 스터디 - 프로그래머스 테이블 해시 함수(python)

문제

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/147354

프로그래머스

 

요약

한 테이블에 대한 해시 함수를 작성한다.

해시 함수는 col, row_begin, row_end를 받으며,

1. col 번째 컬럼을 오름차순으로 (같을 시 0번째 컬럼을 내림차순으로) 정렬하고,

2. row_begin ~ row_end의 각 행의 모든 컬럼에 대해 i번째 컬럼 갑을 i로 나눈 나머지의 합을 구하고,

3. 그 합들을 전부 XOR 한 값을 반환한다.

의식의 흐름

해시 테이블을 한번도 안써봐서 연습겸 고른 문제였는데, 알고보니 테이블 해시였다.

그냥 문제에서 시키는대로 구현하면 된다.

A xor B가 비트가 다르면 1, 같으면 0이라고 외웠었는데,

이건 그냥 특징이고 원래 정의는 1의 수가 홀수인지 짝수인지 였다.

그래서 마지막에 전부 XOR하는 부분도, 하나씩 차례로 XOR하면 된다.

구현

자료구조

따로 만들 자료구조는 없었다.

알고리즘

시키는대로 구현하되, 위에서 언급했듯이 마지막에 모든 합에 대해 XOR을 하는 부분은 2개씩 XOR해도 된다.

(분배법칙이 성립한다.)

코드

python에서 1차 2차 key로 정렬하고 싶을 땐, 각 key를 원소로 하는 튜플을 key로 설정하면 된다.

 

같은 정답률인 양궁게임에 비해 쉬웠지만,

그래도 XOR를 정확히 알고 가니 좋은 수확인 것 같다.

 

def solution(data, col, row_begin, row_end):
    answer = 0
    datas = sorted(data, key = lambda x : (x[col-1], -x[0]))
    for i in range(row_begin-1, row_end):
        total = 0
        for j in range(len(datas[0])):
            total += datas[i][j] % (i+1)
        answer = answer ^ total
    
    return answer