테이블 해시 함수

문제: https://school.programmers.co.kr/learn/courses/30/lessons/147354

문제설명

1. 주어진 파라미터: int[][] data, int col, int row_begin, int row_end
2. 반환값: 테이블의 해시값 int return
3. 해시함수 정의
   • col 기준으로 오름차순 정렬
   • col 값이 동일하면 첫번째 칼럼 기준 내림차순 정렬
   • S_i : i 번째 행의 튜플에 대해 각 칼럼의 값을 i로 나눈 나머지 값들의 합
   • row_begin ≤ i ≤ row_end 에 대한 모든 i의 S_i 를 누적해 bitwise XOR 한 값을 해시값으로 반환

풀이방식

1. 정렬 먼저:

   • col 번째 값을 기준으로 오름 차순 정리
     • data[][] 순서대로 읽으면서 넣어야하는데 알맞은 자기 순서에 들어가야한다. (여러번 중복이 있어도 잘 찾아가야한다.) → 해당 값이랑 들어갈 곳의 존재하는 값들이랑 비교해서 넣어야함 → 자료구조 무엇? ArrayList로 처리
       
     • 같을 시 기본키로 내림차순 정렬

2. S_i 구하기

3. XOR? → 비트 연산 필요

   → ^ 연산자 사용

4. 시작 인덱스가 1부터 시작해서 모든 인덱스에서 1씩 빼줘야한다.

코드

import java.util.*;

class Solution {
    public int solution(int[][] data, int col, int row_begin, int row_end) {

        // 1 -> 0 시작
        col = col - 1;

        // 정렬 (col 기준 오름차순 정렬, 같을 경우 첫 번째 열 기준 내림차순 정렬)
        List<int[]> copy = new ArrayList<>();
        copy.add(data[0]);

        for(int i = 1; i < data.length; i++){
            boolean inserted = false; // 삽입 여부 확인

            for(int j = 0; j < copy.size(); j++){
                int[] current = copy.get(j);

                if(data[i][col] < current[col]){
                    // col 기준 오름차순으로 삽입
                    copy.add(j, data[i]);
                    inserted = true;
                    break;
                }
                else if(data[i][col] == current[col]){
                    if(data[i][0] > current[0]){
                        // col 값이 같을 경우 첫 번째 열 기준 내림차순으로 삽입
                        copy.add(j, data[i]);
                        inserted = true;
                        break;
                    }
                }
            }

            if(!inserted){
                // 모든 기존 요소보다 크거나 같은 경우 리스트의 끝에 추가
                copy.add(data[i]);
            }
        }

        // 3. S_i 계산 
        int answer = 0;
        for (int i = row_begin; i <= row_end; i++) {
            // 1 -> 0 으로 변환
            int index = i - 1;
            if(index >= 0 && index < copy.size()){
                answer ^= calc(copy.get(index), i);
            }
        }

        return answer;
    }

    // S_i 계산
    public int calc(int[] data, int i){
        int sum = 0;
        for(int num : data){
            sum += num % i;
        }
        return sum;
    }
}

회고

1에서 시작한다는 부분을 잡지 못해 많이 헤맨거같다 & 하나는 내림차순, 하나는 오름차순이라 나간 정신 찾으러 갑니다

---

참 쉽쥬잉~?~?