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

문제

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

---

풀이(20분)

import java.util.*;
class Solution {
    public int solution(int[][] data, int col, int row_begin, int row_end) {
        int answer = 0;
        ArrayList<Point> pointList = new ArrayList<>();
        for(int i = 0; i < data.length; i++){
            pointList.add(new Point(i, data[i][0], data[i][col-1]));
        }
        Collections.sort(pointList, (o1, o2) ->{
            int o1Id = o1.id;
            int o2Id = o2.id;
            int o1Col = o1.col;
            int o2Col = o2.col;
            if(o1Col != o2Col){
                return o1Col - o2Col;
            }
            return o2Id - o1Id;
        } );
        
        int sum = 0;
        for(int i = row_begin; i <= row_end; i++){
            Point tempPoint = pointList.get(i-1);
            int tempSum = 0;
            for(int j = 0; j < data[0].length; j++){
                tempSum += data[tempPoint.idx][j] % i;
            }
            sum = sum ^ tempSum;
        }
        answer = sum;
        return answer;
    }

    public static class Point{
        int idx;
        int id;
        int col;

        public Point(int idx, int id, int col){
            this.idx = idx;
            this.id = id;
            this.col = col;
        }
    }
}

 

일단 풀이를 시작하기 앞서 알아둬야 할 두 가지에 대해 먼저 정리하자.

 

1. Collections.sort()

일반적으로 Collections.sort(list) 같이 써서 오름차순 정렬을 하거나, Collections.sort(list, Comparator.reverseOrder()); 같은 내림차순 정렬을 쓸 수 있다.

하지만 옆에 식을 적어줌으로써 내가 원하는 방식의 정렬을 할 수 있다.

 

예를 들어 오름차순의 경우 Collections.sort(list, (o1, o2) -> {return o1 - o2})를 하면 오름차순이 되고, o2-o1을 하면 내림차순이 된다.

여기서 알아두어야 할 것은 음수일 경우 현재 o1과 o2를 유지하고, 양수일 경우 o2와 o1의 순서를 바꾼다고 생각하면 된다.

따라서 풀이에 나온 코드는 다음과 같다.

Collections.sort(pointList, (o1, o2) ->{
            int o1Id = o1.id;
            int o2Id = o2.id;
            int o1Col = o1.col;
            int o2Col = o2.col;
            if(o1Col != o2Col){
                return o1Col - o2Col;
            }
            return o2Id - o1Id;
        } );

 

여기서 PointList는 point를 가지는 리스트이며 idx(원래 data용 인덱스), id, col에 대한 값을 가진다. 이때 문제에서 아래와 같은 조건을 주었다. 테이블의 튜플을 col번째 컬럼의 값을 기준으로 오름차순 정렬을 하되, 만약 그 값이 동일하면 기본키인 첫 번째 컬럼의 값을 기준으로 내림차순 정렬합니다. 따라서, col에 대한 값이 다르다면 o1Col- o2Col을 통해 col 값을 이용한 오름차순 정렬을 해준다. 만약 같다면, o2Id - o1Id를 하여 id 값을 이용한 내림차순 정렬을 해주면 되는 것이다.

 

2. 비트연산자

사실 & | 연산은 알고 있었어도 XOR연산을 지원하는지 처음 알게 되었다.

java에서 제공하는 비트 연산은 대략 다음과 같다.

& (And)

| (Or)

^ (Xor)

<< (Left Shift) : 비트를 왼쪽으로 밀고, 오른쪽에 0을 채운다.

>> (Right Shift) : 비트를 오른쪽으로 밀고, 오른쪽에 부호비트를 채운다.

>>> (Unsigned Right Shift) : 비트를 오른쪽으로 밀고, 부호와 관계없이 왼쪽에 0을 채운다.

---

이제 문제의 로직을 살펴보자.

 

먼저 정렬을 해준 뒤 정렬해준 것의 row_begin 부터 row_end까지의 idx를 꺼내와야 한다.(data는 정렬이 안 되어있으므로)

이후, tempSum에 먼저 mod 연산을 한 합을 구해준 뒤 sum과 XOR 연산을 진행해주면 된다.