Programmers | Level 2 | 테이블 해시 함수

Programmers | Level 2 | 테이블 해시 함수

Problems

• 📘 Src: Programmers
• 🗂️ Cat: Sorting

󰧭 Description

완호가 관리하는 어떤 데이터베이스의 한 테이블은 모두 정수 타입인 컬럼들로 이루어져 있습니다. 테이블은 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 함수를 완성해주세요.

 Constraints

• 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의 길이

󰦕 Examples

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

Solutions

󰘦 Code

import java.util.*;
import java.util.stream.*;

class Solution {
    public int solution(int[][] data, int col, int row_begin, int row_end) {
        // 주어진 데이터를 정렬하는 과정
        List<int[]> table = Arrays.stream(data)
            .sorted((a, b) -> {
                int index = col - 1;
                int diff = a[index] - b[index];  // col번째 컬럼 기준 오름차순
                if (diff != 0) return diff;      // 값이 다르면 그 차이 반환
                return b[0] - a[0];  // 값이 같으면 첫 번째 컬럼을 기준으로 내림차순
            })
            .collect(Collectors.toList());
        
        int hash = 0;  // 해시 값 저장
        for (int i = row_begin; i <= row_end; i++) {
            int[] s = table.get(i - 1);  // i번째 행의 데이터
            int si = 0;  // S_i 값 계산
            for (int j = 0; j < s.length; j++) {
                si += s[j] % i;  // i번째 행의 각 값을 i로 나눈 나머지를 더함
            }
            hash ^= si;  // XOR로 해시 값 누적
        }
        
        return hash;  // 최종 해시 값 반환
    }
}

 Approaches

이 문제는 정렬, 나머지 연산, XOR 연산을 조합하여 주어진 테이블의 해시 값을 계산하는 문제입니다. 각 행에 대해 특정 규칙을 따르면서 값을 계산하고, 그 결과를 누적하여 XOR 연산을 통해 최종 해시 값을 도출합니다.

1. 문제 분석

주어진 문제에서는 테이블을 정렬하고, 그 데이터를 기반으로 해시 값을 계산하는 과정을 요구합니다. 먼저, 테이블은 col번째 컬럼을 기준으로 오름차순으로 정렬되며, 동일한 값이 있을 경우에는 첫 번째 컬럼(기본키)을 기준으로 내림차순으로 정렬합니다.

정렬 후에는 주어진 범위 내의 각 행에 대해 나머지 연산을 수행합니다. i번째 행의 각 값을 i로 나눈 나머지들을 합산하여 S_i 값을 계산하게 됩니다. 이 과정은 행 번호와 값 간의 관계를 나타내는 독특한 패턴을 형성합니다.

그렇게 계산된 S_i 값들은 XOR 연산을 통해 누적됩니다. XOR(배타적 논리합) 연산은 두 값이 같으면 0, 다르면 1을 반환하는 이진 연산입니다. XOR 연산의 특징은 같은 값을 여러 번 XOR하면 그 값이 사라지는 특성이 있어, 중복된 값이 최종 해시 값에 영향을 주지 않도록 합니다. 이를 통해 고유한 해시 값을 도출하는 것이 목표입니다.

2. 접근 방식

이 문제의 해결은 크게 정렬, 나머지 연산을 통한 S_i 값 계산, 그리고 XOR을 사용한 해시 값 도출의 세 가지 주요 단계로 나눌 수 있습니다. 각 단계를 하나씩 설명하면 다음과 같습니다.

1. 테이블 정렬: 주어진 테이블을 col번째 컬럼을 기준으로 오름차순 정렬합니다. 이때, col번째 컬럼 값이 같을 경우에는 첫 번째 컬럼(기본키)을 기준으로 내림차순으로 정렬해야 합니다. 이 단계에서는 우선 col번째 컬럼을 기준으로 차이를 계산하고, 만약 값이 동일하다면 기본키의 값으로 내림차순 정렬을 수행합니다.
2. 범위 내 S_i 값 계산: 정렬된 테이블에서 주어진 row_begin부터 row_end까지의 행에 대해 S_i 값을 계산해야 합니다. S_i는 i번째 행의 각 값을 i로 나눈 나머지들을 모두 더한 값입니다. 이를 계산하려면 각 행의 각 값을 해당 행 번호로 나눈 나머지를 구하고, 이 나머지들의 합을 구해 S_i 값을 도출합니다. 여기서는 반복문을 통해 각 행의 데이터를 가져오고, 각 컬럼 값을 나머지 연산을 통해 처리합니다.
3. XOR 연산을 통한 해시 값 도출: 계산된 S_i 값들을 XOR 연산으로 누적합니다. XOR 연산의 특징을 활용하여 중복된 값이 제거되며, 누적된 값이 최종 해시 값이 됩니다. 이 과정에서는 S_i 값들을 차례로 XOR 연산을 수행하며, 누적된 값을 갱신합니다.

이를 통해 모든 행의 S_i 값을 계산한 후, 최종적으로 XOR 연산을 통해 고유한 해시 값을 구할 수 있습니다.

3. 테이블 정렬

먼저 테이블을 col번째 컬럼을 기준으로 정렬합니다. 여기서 첫 번째 정렬 기준은 col번째 컬럼의 값을 오름차순으로 정렬하는 것입니다. 만약 col번째 컬럼의 값이 동일하다면, 기본키인 첫 번째 컬럼을 기준으로 내림차순으로 정렬합니다. 이 정렬 규칙에 따라 데이터를 정렬하면, 후속 작업을 위한 정렬된 테이블을 얻게 됩니다.

정렬을 수행할 때는 두 가지 조건을 고려해야 합니다:

• col번째 컬럼을 기준으로 오름차순 정렬.
• 동일한 값이 있을 경우, 기본키(첫 번째 컬럼)를 기준으로 내림차순 정렬.

List<int[]> table = Arrays.stream(data)
    .sorted((a, b) -> {
        int index = col - 1;  // col번째 컬럼 인덱스
        int diff = a[index] - b[index];  // col번째 컬럼 값 비교
        if (diff != 0) return diff;  // col 값이 다르면 오름차순 정렬
        return b[0] - a[0];  // col 값이 같으면 첫 번째 컬럼 기준으로 내림차순 정렬
    })
    .collect(Collectors.toList());

4. 정렬된 테이블에서 S_i 계산

테이블이 정렬된 후, 주어진 범위 내의 각 행에 대해 S_i 값을 계산해야 합니다. S_i는 i번째 행의 각 값을 i로 나눈 나머지들의 합으로 정의됩니다. 즉, 각 행의 각 값을 해당 행 번호로 나누고, 그 나머지 값을 모두 더하여 S_i를 구하는 방식입니다.

이 과정에서는 주어진 범위 내의 각 행을 차례로 탐색합니다. 각 행의 데이터는 2차원 배열로 되어 있으므로, 해당 행의 각 값을 행 번호로 나눈 후 그 나머지를 모두 더해 S_i 값을 계산합니다. 이때 나머지 연산을 사용해 각 값을 i로 나눈 값을 구하고, 이를 누적하여 하나의 값을 만듭니다.

계산된 S_i 값은 XOR 연산으로 누적됩니다. XOR 연산은 중복된 값을 효과적으로 처리할 수 있어, 모든 S_i 값들을 결합하여 최종 해시 값을 구하는 데 유용합니다. 최종적으로, 모든 범위 내 행에서 계산된 S_i 값을 XOR 연산으로 결합하여 최종 해시 값을 도출합니다.

int hash = 0;  // 해시 값 저장
for (int i = row_begin; i <= row_end; i++) {
    int[] s = table.get(i - 1);  // i번째 행의 데이터
    int si = 0;  // S_i 값 계산
    for (int j = 0; j < s.length; j++) {
        si += s[j] % i;  // i번째 행의 각 값을 i로 나눈 나머지를 더함
    }
    hash ^= si;  // XOR로 해시 값 누적
}

5. 최종 해시 값 계산

모든 행의 S_i 값이 계산된 후, 이 값들을 XOR 연산으로 누적한 값이 최종 해시 값이 됩니다. XOR 연산은 중복된 값의 해시를 구별하기 위한 방법으로, 최종 해시 값을 도출하는 데 유용하게 사용됩니다.

// 최종 해시 값 반환
return hash;

󰄉 Complexity

• ⏳ TC: O(n log n)
• 💾 SC: O(n)

정렬에 걸리는 시간은 O(n log n)이며, 나머지 연산과 XOR 계산은 n의 크기에 비례하므로, 시간 복잡도에서 크게 영향을 주지 않습니다. 따라서 시간 복잡도는 테이블의 행 수 n에 대한 정렬 시간이 지배적이므로 O(n log n)입니다. 공간 복잡도는 주어진 데이터를 저장하는 테이블의 크기와 정렬된 결과를 저장하기 위한 공간이 필요하므로, n개의 행을 처리하는 데 O(n)의 공간을 사용합니다.