[프로그래머스] 테이블 해시 함수 (Java)

프로그래머스 : 테이블 해시 함수 (Java)

문제

문제 확인하기

풀이

문제의 요구사항에 따라 알고리즘의 흐름을 작성해보자.

1. 테이블(배열)을 정렬한다.
   1. col번째 컬럼을 기준으로 오름차순 정렬한다.
   2. 같은 값은 첫번째 컬럼인 기본키를 기준으로 내림차순 정렬한다.
2. 각 튜플에 대해 아래 내용을 반복한다.
   • 각 컬럼을 현재 튜플의 순서(i)로 나눈 나머지를 구한다.
   • 나머지들의 합을 S_i로 구한다.
3. 각 튜플의 순서를 i라고 할 때, row_begin <= i <= row_end인 모든 S_i를 누적하여 XOR 연산하고 이를 리턴한다.

2, 3번 과정을 통합하여 다음과 같이 최적화 할 수 있다.

2. 튜플의 순서를 i라고 할 때, row_begin <= i <= row_end를 만족하는 튜플들에 대해 아래 내용을 반복한다.
   • 각 컬럼을 현재 튜플의 순서(i)로 나눈 나머지를 구한다.
   • 나머지들의 합을 S_i로 구한다.
   • 이전 반복의 S_i와 XOR 연산한다.
3. XOR 연산의 결과를 리턴한다.

여기서 주의할 점은, 문제에서 말하는 i번째와 코드로 주어진 data 배열의 인덱스가 완전히 일치하지는 않다는 것이다.
문제에서 설명하는 기본키 컬럼은 첫 번째 컬럼으로 i = 1일 때이다.
코드로 주어진 data 배열에서 첫 번째 컬럼은 i = 0이다.
따라서 k번째 요소에 대해 배열로 접근할 때에는 k-1 인덱스에 접근해야 한다.

자바 코드로 작성한 풀이는 아래와 같다.

public class TableHashFunction {
    public int solution(int[][] data, int col, int row_begin, int row_end) {
        int answer = 0;

        // col 번째 컬럼(data[i][col])을 기준으로 오름차순 정렬, 같은 값은 첫번째 컬럼인 기본키(data[i][0])를 기준으로 내림차순 정렬
        // 배열은 0부터 시작하고, 문제에서는 1부터 시작함. 따라서 코드에서는 col-1이 문제의 col 과 같다.
        Arrays.sort(data, ((o1, o2) -> o1[col - 1] != o2[col - 1] ? o1[col - 1] - o2[col - 1] : o2[0] - o1[0]));
        // 모든 튜플에 대해 반복 수행
        for (int i = row_begin - 1; i <= row_end - 1; i++) {
            int S_i = 0;
            // 각 컬럼을 i+1로 나눈 값을 더함
            for (int d : data[i]) S_i += (d % (i + 1));
            // XOR 누적
            answer = (answer ^ S_i);
        }

        return answer;
    }
}