테이블 해시 함수

https://school.programmers.co.kr/learn/courses/30/lessons/147354?language=python3 

프로그래머스

---

try1

문제 설명만 보고 이해하기 어려웠던 문제였던 것 같다.

그래도 다행히 예시를 보고 이해했다.

이해를 한 후 크게 알고리즘을 3가지로 나눴다.

1. 전체 data 정렬

2. S_i들의 나머지들 합 구하기

3. bitwise XOR

 

※ 나의 코드

def solution(data, col, row_begin, row_end):
    answer = 0
    
    # 전체 정렬
    S_data = sorted(data, key = lambda x:(x[col-1], -x[0]))
	
    # S_i들의 나머지 합 구하기
    i = row_begin
    for S in S_data[row_begin-1:row_end]:
        S_i = 0
        for v in S:
            S_i += v % i     
        # bitwise XOR
        answer = (S_i)^answer
        i += 1

    return answer

 

 

문제 풀이)

sorted key를 이용하여 첫번째 기준 x[col-1]으로 오름차순, x[0]에 -를 붙여서 두번째 기준 x[0]으로 내림차순으로 정렬함

i에 시작 col값인 row_begin을 넣음

row_begin과 row_end를 이용하여 구해야할 튜플의 범위만큼 for문으로 돌림

처음에 S_i에 0을 할당하고 해당 순서의 튜플을 for문으로 돌면서 해당 i를 나눈 나머지를 S_i에 더해줌

해당 순서의 튜플을 도는 for문이 끝나면 해당 순서의 S_i는 구해짐

구해진 S_i을 ^연산자를 이용하여 answer과 bitwise XOR을 함

제일 첫번째 S_i로 하는 bitwise XOR은 answer이 0이므로 첫번째 S_i가 answer에 그대로 넣어짐

bitwise XOR을 하고나면 i에 1을 더해줌

이런식으로 S_data[row_begin-1:row_end]를 도는 for문이 돌면서

해당 순서의 S_i는 그 이전 S_i들의 bitwise XOR한 결과들과 bitwise XOR을 함으로써

우리가 원하는 결과 answer을 얻을 수 있음

 

테스트 결과) - 총합 232.03ms

테스트 1 〉	통과 (0.01ms, 10.2MB)
테스트 2 〉	통과 (0.04ms, 10.4MB)
테스트 3 〉	통과 (0.06ms, 10.2MB)
테스트 4 〉	통과 (0.13ms, 10.3MB)
테스트 5 〉	통과 (1.24ms, 12MB)
테스트 6 〉	통과 (31.95ms, 57.8MB)
테스트 7 〉	통과 (28.35ms, 64.5MB)
테스트 8 〉	통과 (59.55ms, 64.4MB)
테스트 9 〉	통과 (64.52ms, 64.4MB)
테스트 10 〉	통과 (46.17ms, 64.2MB)
테스트 11 〉	통과 (0.01ms, 9.95MB)