완호가 관리하는 어떤 데이터베이스의 한 테이블은 모두 정수 타입인 컬럼들로 이루어져 있습니다. 테이블은 2차원 행렬로 표현할 수 있으며 열은 컬럼을 나타내고, 행은 튜플을 나타냅니다.
첫 번째 컬럼은 기본키로서 모든 튜플에 대해 그 값이 중복되지 않도록 보장됩니다. 완호는 이 테이블에 대한 해시 함수를 다음과 같이 정의하였습니다.
col
, row_begin
, row_end
을 입력으로 받습니다.col
번째 컬럼의 값을 기준으로 오름차순 정렬을 하되, 만약 그 값이 동일하면 기본키인 첫 번째 컬럼의 값을 기준으로 내림차순 정렬합니다.row_begin
≤ i ≤ row_end
인 모든 S_i를 누적하여 bitwise XOR 한 값을 해시 값으로서 반환합니다.테이블의 데이터 data
와 해시 함수에 대한 입력 col
, row_begin
, row_end
이 주어졌을 때 테이블의 해시 값을 return 하도록 solution 함수를 완성해주세요.
data
의 길이 ≤ 2,500data
의 원소의 길이 ≤ 500data
[i][j] ≤ 1,000,000
data
[i][j]는 i + 1 번째 튜플의 j + 1 번째 컬럼의 값을 의미합니다.data
의 원소의 길이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,2,6],[1,5,10],[4,2,9],[3,8,3]], 2, 2, 3
col
번째(2번째) 컬럼값을 기준으로 오름차순 정렬 4 2 9
2 2 6
1 5 10
3 8 3
row_begin
부터 row-end
까지 i번째 행을 i로 나눈 나머지 합 구하기2%2 + 2%2 + 6%2 = 0
1%3 + 5%3 + 10%3 = 4
0 XOR 4 = 4
XOR 연산은 두 값의 각 자릿수를 비교해 값이 0으로 같으면 0, 값이 1로 같으면 0, 다르면 1을 계산한다.
0101 XOR 0011 = 0110
x = y ^ z;
https://iamsjy17.github.io/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98_%EA%B8%B0%EC%B4%88/2019/05/09/bitop.html
function solution(data, col, row_begin, row_end) {
let sum_list = [];
// 1. col번째 컬럼값을 기준으로 오름차순 정렬, 값이 동일하면 첫 번째 컬럼값 기준으로 내림차순
data.sort((a,b) => a[col - 1] === b[col - 1] ? b[0] - a[0] : a[col - 1] - b[col - 1]);
// 2. row_begin부터 row-end까지 i번째 행을 i로 나눈 나머지의 합 구하기
for(let i=row_begin-1;i<row_end;i++){
sum_list.push(data[i].reduce((acc,cur) => acc + cur % (i+1),0));
}
// 각 자리수가 다르면 1, 나머지 0, 자리부족하면 0으로 채우기
let answer = sum_list.reduce((acc,cur) => {
let xor = '';
let acc_binary = acc.toString(2);
let cur_binary = cur.toString(2);
if(acc_binary.length < cur_binary.length){
acc_binary = '0'.repeat(cur_binary.length - acc_binary.length) + acc_binary;
}else if(acc_binary.length > cur_binary.length){
cur_binary = '0'.repeat(acc_binary.length - cur_binary.length) + cur_binary;
}
for(let i=0;i<acc_binary.length;i++){
xor += acc_binary[i] !== cur_binary[i] ? '1' : '0';
}
return xor;
},0)
return parseInt(answer,2);
}
^
를 이용해 XOR 계산을 단축시켰다.
function solution(data, col, row_begin, row_end) {
let sum_list = [];
// 1. col번째 컬럼값을 기준으로 오름차순 정렬, 값이 동일하면 첫 번째 컬럼값 기준으로 내림차순
data.sort((a,b) => a[col - 1] === b[col - 1] ? b[0] - a[0] : a[col - 1] - b[col - 1]);
// 2. row_begin부터 row-end까지 i번째 행을 i로 나눈 나머지의 합 구하기
for(let i=row_begin-1;i<row_end;i++){
sum_list.push(data[i].reduce((acc,cur) => acc + cur % (i+1),0));
}
// 3. XOR 계산
return sum_list.reduce((acc,cur) => acc ^ cur,0);
}
function sort(a, b, col) {
return a[col - 1] - b[col - 1] || b[0] - a[0];
}
function solution(data, col, row_begin, row_end) {
data.sort((a, b) => sort(a, b, col));
return data
.map((row, i) => row.reduce((acc, col) => acc + (col % (i + 1)), 0))
.slice(row_begin - 1, row_end)
.reduce((acc, val) => acc ^ val, 0);
}