99클럽 코테 스터디 6일차 TIL + Arrays.sort/[프로그래머스] 테이블 해시 함수

 

💡문제

[level 2] 테이블 해시 함수 - 147354

문제 링크

성능 요약

메모리: 144 MB, 시간: 9.92 ms

 

 

---

🤔접근법

문제 요약

• 주어진 2차원 배열을 정해진 컬럼을 오름차순으로 행을 다시 정렬 (값이 같다면 첫번째 값을 기준으로 내림차순)
• i ~ j 행을 각 i 행으로 나눈 나머지들의 합을 구한후 그 합들을 XOR 연산 하여 나온 값을 출력

범위 체크 및 시간복잡도 예상

• 1 ≤ data의 길이 ≤ 2,500
• 1 ≤ data의 원소의 길이 ≤ 500
• 1 ≤ data[i][j] ≤ 1,000,000
  • data[i][j]는 i + 1 번째 튜플의 j + 1 번째 컬럼의 값을 의미합니다. (주어진 입력값들은 모두 1부터 인덱스가 시작함으로 유의하자)
• 1 ≤ col ≤ data의 원소의 길이
• 1 ≤ row_begin ≤ row_end ≤ data의 길이
• 배열들의 원소를 모두 훑어도 가능한 시간 , 혹시나 정렬로 인해서 N^2 의 시간이 필요하다해도 가능
• $O(data의 길이^2)$ 까지도 가능

풀이법

로직은 어렵지 않다. 주어진 col 값을 기준으로 오름차순 정렬

만약 값이 같다면 첫번째 컬럼을 기준으로 내림차순,

이후 i ~ j 의 각 행의 컬럼들 값을 i 값으로 나머지 연산한 값들을 합한다.

이후 각 행들을 가지고 나온 값들을 xor 연산하면 된다.

어렵지 않은 과정인데 나는 2차원 배열을 다시 정렬하는 과정이 복잡할거라 생각되어

각 행들을 담고 있는 객체를 만들었고 그 객체에 Comparable 를 상속받아 compareTo 오버라이드 하여 객체를 담은 배열을 정렬하였다.

🔑 Arrays.sort( T[] a, Comparator<? super T> c )를 이용하여 우선순위 조건을 적용하여 정렬하자

그러나 Arrays.sort에 위와 같이 비교 조건을 담을 수 있다.

람다식 작성이 익숙하지 않아서 약간의 도움을 받았다.

다음에는 배열을 특정 조건에 따라 정렬할때 써먹어야겠다.위만 노래번호를 새로운 list에 담는다.

➡️ 해당 풀이법의 시간 복잡도 : $O(NlogN)$

 

 

---

😎SUCCESS

고냥 단박에 성공

 

---

👩‍💻 코드

• 기존 코드

import java.util.*;

class Solution {
    public class Row implements Comparable<Row>{
        int key; // key 기준 내림차순
        int colValue; // col 기준 오름차순
        int []row;

        public Row(int[] row, int col){
            this.row = row;
            key = row[0];
            colValue = row[col];
        }

        @Override
        public int compareTo(Row o) {
            if(o.colValue == this.colValue){
                return o.key - this.key;
            }
            return this.colValue - o.colValue;
        }

        public int sum(int i) {
            int result = 0;
            for (int j = 0; j < row.length; j++) {
                result += row[j] % i;
            }
            return result;
        }
    }
    public int solution(int[][] data, int col, int row_begin, int row_end) {
        int h = data.length;

        Row rows[] = new Row[h];
        for (int i = 0; i < h; i++) {
            rows[i] = new Row(data[i], col-1);
        }

        Arrays.sort(rows);

        int answer = 0;
        
        for (int i = row_begin-1; i < row_end; i++) {
            answer = answer ^ rows[i].sum(i+1);
        }

        return answer;
    }
}

• 리팩토링 코드

import java.util.*;

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

            Arrays.sort(data, (o1, o2) -> {
                if(o1[col-1] == o2[col-1]){
                    return o2[0] - o1[0];
                }
                return o1[col-1] - o2[col-1];
            } );

            int answer = 0;

            for (int i = row_begin-1; i < row_end; i++) {
                int sum = 0;
                for (int j = 0; j < data[i].length; j++) {
                    sum += data[i][j] % (i+1);
                }
                answer = answer ^ sum;
            }

            return answer;
        }
}