프로그래머스 테이블 해시 함수

문제 설명

완호가 관리하는 어떤 데이터베이스의 한 테이블은 모두 정수 타입인 컬럼들로 이루어져 있습니다. 테이블은 2차원 행렬로 표현할 수 있으며 열은 컬럼을 나타내고, 행은 튜플을 나타냅니다.
첫 번째 컬럼은 기본키로서 모든 튜플에 대해 그 값이 중복되지 않도록 보장됩니다. 완호는 이 테이블에 대한 해시 함수를 다음과 같이 정의하였습니다.

1. 해시 함수는 col, row_begin, row_end을 입력으로 받습니다.
2. 테이블의 튜플을 col번째 컬럼의 값을 기준으로 오름차순 정렬을 하되, 만약 그 값이 동일하면 기본키인 첫 번째 컬럼의 값을 기준으로 내림차순 정렬합니다.
3. 정렬된 데이터에서 S_i를 i 번째 행의 튜플에 대해 각 컬럼의 값을 i 로 나눈 나머지들의 합으로 정의합니다.
4. row_begin ≤ i ≤ row_end 인 모든 S_i를 누적하여 bitwise XOR 한 값을 해시 값으로서 반환합니다.

테이블의 데이터 data와 해시 함수에 대한 입력 col, row_begin, row_end이 주어졌을 때 테이블의 해시 값을 return 하도록 solution 함수를 완성해주세요.

제한 사항

• 1 ≤ data의 길이 ≤ 2,500
• 1 ≤ data의 원소의 길이 ≤ 500
• 1 ≤ data[i][j] ≤ 1,000,000
  • data[i][j]는 i + 1 번째 튜플의 j + 1 번째 컬럼의 값을 의미합니다.
• 1 ≤ col ≤ data의 원소의 길이
• 1 ≤ row_begin ≤ row_end ≤ data의 길이

입출력 예

data	col	row_begin	row_end	result
[[2,2,6],[1,5,10],[4,2,9],[3,8,3]]	2	2	3	4

입출력 예 설명

• 정해진 방법에 따라 튜플을 정렬하면 {4, 2, 9}, {2, 2, 6}, {1, 5, 10}, {3, 8, 3} 이 됩니다.
• S_2 = (2 mod 2) + (2 mod 2) + (6 mod 2) = 0 입니다.
• S_3 = (1 mod 3) + (5 mod 3) + (10 mod 3) = 4 입니다.
• 따라서 해시 값은 S_2 XOR S_ 3 = 4 입니다.

풀이

이 문제는...

• 그냥 지문대로 코딩해서 풀면 풀리는 문제다.
• 뭔가 대단한 게 있을 줄 알았는데...

def solution(data, col, row_begin, row_end):
    sum_xor = 0
    data.sort(key=lambda x:(x[col-1],-x[0]))
    col_size = len(data[0])
    
    for c in range(col_size):
        sum_xor += data[row_begin-1][c] % row_begin
    #print(data[row_begin-1], sum_xor)
    
    for i in range(row_begin, row_end, 1):
        sum_mod = 0
        for c in range(col_size):
            sum_mod += data[i][c] % (i+1)
        sum_xor = sum_xor ^ sum_mod
        #print(data[row_begin-1], sum_mod)
    return sum_xor
    
정확성  테스트
테스트 1 〉	통과 (0.02ms, 10.3MB)
테스트 2 〉	통과 (0.03ms, 10.2MB)
테스트 3 〉	통과 (0.06ms, 10.4MB)
테스트 4 〉	통과 (0.24ms, 10.3MB)
테스트 5 〉	통과 (1.37ms, 12.1MB)
테스트 6 〉	통과 (33.16ms, 57.8MB)
테스트 7 〉	통과 (45.04ms, 64.5MB)
테스트 8 〉	통과 (57.18ms, 64.4MB)
테스트 9 〉	통과 (69.37ms, 64.5MB)
테스트 10 〉	통과 (80.05ms, 64.3MB)
테스트 11 〉	통과 (0.01ms, 10.3MB)

• 혹시나 해서 짝수개면 어차피 0이니까 카운터로 모아서 처리해보았지만 속도 체크에서 별 차이없거나 더 느려짐.
• 그냥 무지성 코딩이 정답.

from collections import Counter

def solution(data, col, row_begin, row_end):
    sum_xor = 0
    data.sort(key=lambda x:(x[col-1],-x[0]))

    mod_counter = Counter()
    for i in range(row_begin-1, row_end):
        row_mod = 0
        for c in range(len(data[0])):
            row_mod += data[i][c] % (i+1)
        mod_counter[row_mod] += 1

    for mod_val, count in mod_counter.items():
        if count % 2 != 0:
            sum_xor ^= mod_val
    
    return sum_xor
    
정확성  테스트
테스트 1 〉	통과 (0.03ms, 10.3MB)
테스트 2 〉	통과 (0.07ms, 10.3MB)
테스트 3 〉	통과 (0.08ms, 10.2MB)
테스트 4 〉	통과 (0.24ms, 10.3MB)
테스트 5 〉	통과 (1.46ms, 12MB)
테스트 6 〉	통과 (36.10ms, 57.7MB)
테스트 7 〉	통과 (51.89ms, 64.5MB)
테스트 8 〉	통과 (73.27ms, 64.4MB)
테스트 9 〉	통과 (76.26ms, 64.6MB)
테스트 10 〉	통과 (76.45ms, 64.2MB)
테스트 11 〉	통과 (0.02ms, 10.1MB)

• 파이썬은 코드 라인 수가 줄어들면 속도가 빨라진다.
• 왜 그럴까?

from collections import Counter

def solution(data, col, row_begin, row_end):
    sum_xor = 0
    data.sort(key=lambda x:(x[col-1],-x[0]))

    mod_counter = Counter()
    for i in range(row_begin-1, row_end):
        row_mod = 0
        row_mod = sum(data[i][c] % (i+1) for c in range(len(data[0])))
        mod_counter[row_mod] += 1

    for mod_val, count in mod_counter.items():
        if count % 2 != 0:
            sum_xor ^= mod_val
    
    return sum_xor
    
정확성  테스트
테스트 1 〉	통과 (0.06ms, 10.2MB)
테스트 2 〉	통과 (0.04ms, 10.4MB)
테스트 3 〉	통과 (0.08ms, 10.1MB)
테스트 4 〉	통과 (0.51ms, 10.4MB)
테스트 5 〉	통과 (1.43ms, 12.1MB)
테스트 6 〉	통과 (30.97ms, 57.8MB)
테스트 7 〉	통과 (46.71ms, 64.6MB)
테스트 8 〉	통과 (58.16ms, 64.5MB)
테스트 9 〉	통과 (69.12ms, 64.6MB)
테스트 10 〉	통과 (72.41ms, 64MB)
테스트 11 〉	통과 (0.01ms, 10.2MB)

• 고수의 알고리즘. 뭔지 모르겠네.

from functools import reduce

def solution(data, col, row_begin, row_end):
    data.sort(key = lambda x : (x[col-1], -x[0]))
    return reduce(lambda x, y: x ^ y,
                  [sum(map(lambda x: x%(i+1), data[i])) for i in range(row_begin-1, row_end)])
                  
정확성  테스트
테스트 1 〉	통과 (0.03ms, 10.3MB)
테스트 2 〉	통과 (0.04ms, 10.3MB)
테스트 3 〉	통과 (0.06ms, 10.1MB)
테스트 4 〉	통과 (0.22ms, 10.4MB)
테스트 5 〉	통과 (1.99ms, 12.1MB)
테스트 6 〉	통과 (30.25ms, 57.8MB)
테스트 7 〉	통과 (45.84ms, 64.4MB)
테스트 8 〉	통과 (57.02ms, 64.3MB)
테스트 9 〉	통과 (64.75ms, 64.5MB)
테스트 10 〉	통과 (72.42ms, 64.2MB)
테스트 11 〉	통과 (0.01ms, 10.2MB)

• reduce가 뭐지?
  • 코딩 도장 - 좋구나.
  • https://dojang.io/mod/page/view.php?id=2360

파이썬 코딩 도장: 32.2 람다 표현식과 map, filter, reduce 함수 활용하기

• 달레서
  • https://www.daleseo.com/python-functools-reduce/
  • 파이썬의 functools 내장 모듈의 reduce() 함수는 여러 개의 데이터를 대상으로 주로 누적 집계를 내기 위해서 사용합니다. 기본 문법은 다음과 같은데요. 기본적으로 초기값을 기준으로 데이터를 루프 돌면서 집계 함수를 계속해서 적용하면서 데이터를 누적하는 방식으로 작동합니다. reduce(집계 함수, 순회 가능한 데이터[, 초기값]) 여기서, 집계 함수는 두개의 인자를 받아야 하는데요. 첫번째 인자는 누적자(accumulator), 두번째 인자는 현재값(current value)가 넘어오게 됩니다. 누적자는 함수 실행의 시작부터 끝까지 계속해서 재사용되는 값이고, 현재값은 루프 돌면서 계속해서 바뀌는 값입니다.

파이썬 reduce 함수 사용법