🎯문제
완호가 관리하는 어떤 데이터베이스의 한 테이블은 모두 정수 타입인 컬럼들로 이루어져 있습니다. 테이블은 2차원 행렬로 표현할 수 있으며 열은 컬럼을 나타내고, 행은 튜플을 나타냅니다.
첫 번째 컬럼은 기본키로서 모든 튜플에 대해 그 값이 중복되지 않도록 보장됩니다. 완호는 이 테이블에 대한 해시 함수를 다음과 같이 정의하였습니다.
- 해시 함수는 col, row_begin, row_end을 입력으로 받습니다.
- 테이블의 튜플을 col번째 컬럼의 값을 기준으로 오름차순 정렬을 하되, 만약 그 값이 동일하면 기본키인 첫 번째 컬럼의 값을 기준으로 내림차순 정렬합니다.
- 정렬된 데이터에서 S_i를 i 번째 행의 튜플에 대해 각 컬럼의 값을 i 로 나눈 나머지들의 합으로 정의합니다.
- row_begin ≤ i ≤ row_end 인 모든 S_i를 누적하여 bitwise XOR 한 값을 해시 값으로서 반환합니다.
테이블의 데이터 data와 해시 함수에 대한 입력 col, row_begin, row_end이 주어졌을 때 테이블의 해시 값을 return 하도록 solution 함수를 완성해주세요.
제한 사항
- 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의 길이
입출력 예
| data | col row_begin | row_end | result |
|---|---|---|---|
| [[2,2,6],[1,5,10],[4,2,9],[3,8,3]] | 2 | 2 | 3 |
입출력 예 설명
- 정해진 방법에 따라 튜플을 정렬하면 {4, 2, 9}, {2, 2, 6}, {1, 5, 10}, {3, 8, 3} 이 됩니다.
- S_2 = (2 mod 2) + (2 mod 2) + (6 mod 2) = 0 입니다.
- S_3 = (1 mod 3) + (5 mod 3) + (10 mod 3) = 4 입니다.
- 따라서 해시 값은 S2 XOR S 3 = 4 입니다.
✏️풀이
코드
import java.util.*;
class Solution {
public int solution(int[][] data, int col, int row_begin, int row_end) {
int answer = 0;
// 각 행마다 col을 기준으로 오름차순 정렬
// 동일하다면 첫번째 열을 기준으로 내림차순 정렬
Arrays.sort(data, ((o1, o2) -> o1[col-1] != o2[col-1] ? o1[col-1] - o2[col-1] : o2[0] - o1[0]));
// S_i 구하기
for(int i = row_begin - 1; i < row_end; i++) {
int S_i = 0;
// S_i에 mod 계산을 한 값을 모두 더해줌
for(int num : data[i]) {
S_i += num % (i+1);
}
// XOR 연산을 한 뒤 저장
answer ^= S_i;
}
return answer;
}
}설명
배열의 정렬을 사용하는 문제였다.
다만 조금 어려운 것이 있다면 2차원 배열을 내가 원하는 순서대로 정렬을 해주는 부분이었다.
data[i][j]는 i+1번째 튜플의 j+1번째 컬럼의 값을 의미한다. 배열의 인덱스는 0부터 시작이므로 col=2라고 하면 실질적으로 data[i][col-1]을 뜻하는 것이다.
따라서 각 행마다 col을 기준으로 오름차순 정렬을 할 때 col-1을 넣어주는 것이 중요하다.
o1[col-1]과 o2[col-1]의 값이 같지 않다면 오름차순 정렬을 진행하고 값이 같다면 튜플의 1번째 컬럼의 값을 기준으로 내림차순 정렬을 진행한다.
이후 정렬이 된 2차원 배열을 가지고 S_i를 구해준다. 이때 row_begin과 row_end도 실질적인 배열의 인덱스보다 1씩 큰 값이므로 잘 생각해서 조건문을 만들어주어야한다.
row_begin-1부터 row_end-1까지 반복을 진행하며 해당 튜플의 모든 컬럼의 값을 i+1과 나머지 연산을 진행한다. 나머지 연산을 진행해서 나온 모든 값을 S_i에 저장을 해준 뒤 answer와 XOR 연산을 진행하고, answer에 그 값을 저장한다.
이처럼 위의 과정을 반복한 뒤에 나온 answer의 값을 반환해주면 문제를 해결할 수 있다!
💡느낀 점
생각보다 간단하게 풀 수 있었다. 배열의 정렬만 제대로 해준다면 그 뒤의 계산은 쉽게 할 수 있어서 정렬을 해주는 부분에서 고민을 좀 했다. 전에 비슷한 방식으로 풀었던 문제들이 생각나서 코드를 짰다. 근데 하다보니 인덱스 부분이 헷갈려서 정렬이 제대로 되지 않았고, 결국 직접 출력을 시켜보면서 정렬이 됐는지 확인하며 풀었다.. 인덱스는 해도해도 헷갈리는 것 같다..
링크
