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

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

문제

문제 설명

완호가 관리하는 데이터베이스 테이블은 정수형 컬럼들로만 구성되어 있으며,
행은 튜플을 나타내고, 열은 컬럼을 의미합니다.

• 첫 번째 컬럼은 기본키 역할을 하며, 모든 튜플에 대해 값이 중복되지 않습니다.
• 완호가 정의한 해시 함수는 다음과 같은 규칙을 가집니다.
• 입력값: col, row_begin, row_end
• 정렬 규칙: col번째 컬럼 기준으로 오름차순 정렬, 동일하면 첫 번째 컬럼은 내림차순 정렬
• 정렬된 결과에서 i번째 행(1부터 시작)에 대해 \( S_i = \sum (컬럼값 \mod i) \)
• 최종 해시 값 = \( S_{row\_begin} \oplus S_{row\_begin+1} \oplus ... \oplus S_{row\_end} \)

제한 사항

• 1 ≤ data 길이 ≤ 2,500
• 1 ≤ data[i] 길이 ≤ 500
• 1 ≤ data[i][j] ≤ 1,000,000
• 1 ≤ col ≤ 컬럼 개수
• 1 ≤ row_begin ≤ row_end ≤ 행 개수

테스트케이스

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

작동 과정 설명

• col=2 기준 오름차순, 같으면 첫 번째 컬럼 내림차순 정렬
• 정렬 결과: {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 \oplus S_3 = 0 \oplus 4 = 4 \)

아이디어

• 정렬 규칙 반영: col번째 열을 기준으로 오름차순, tie-breaker로 첫 번째 열을 내림차순 → data.sort(key=lambda x: (x[col-1], -x[0]))
• S_i 계산: i번째 행(1-indexed)에서 모든 열에 대해 (값 % i) 합산
• XOR 연산 누적: 파이썬에서 XOR은 ^ 연산자 사용, 누적 XOR 연산은 순서와 상관없이 동일한 결과

전체코드

def solution(data, col, row_begin, row_end):
    answer = 0
    data.sort(key=lambda x: (x[col-1], -x[0]))
    N = len(data)
    M = len(data[0])
    S = []
    
    for i in range(row_begin, row_end+1):
        s = 0
        for j in range(M):
            s += data[i-1][j] % i
        S.append(s)
    
    answer = S[0]
    n = len(S)
    for i in range(1, n):
        answer = answer ^ S[i]
    
    return answer

결론

• 이 문제의 핵심은 정렬 기준, 나머지 연산, XOR 누적입니다.
• 정렬 기준이 이중 조건이라는 점이 중요합니다. (col 오름차순 → 첫 번째 컬럼 내림차순)
• i번째 행에서 행 번호(i)를 나누는 기준으로 사용한다는 점도 유의해야 합니다.
• 마지막에는 단순 합이 아니라 XOR 연산으로 누적해야 정답이 나옵니다.
• 즉, 정렬을 정확히 구현하고, 인덱스에 맞춰 나머지 연산을 수행하며, 결과를 XOR로 누적하면 문제를 해결할 수 있습니다.