KiTFOx's Notepad 📝

1. 문제 요약

열은 컬럼, 행은 튜플
첫번째 컬럼은 기본키로서 모든 튜플에 대해 그 값이 중복되지 않도록 보장

(요약하자면 id 같은 고유 번호라는 것)

1. 해시 함수는 col, row_begin, row_end 을 입력으로 받음
2. 테이블의 튜플(행)을 col번째 컬럼의 값을 기준으로 오름차순 정렬을 하되, 
만약 그 값이 동일하면 기본키인 첫 번째 컬럼의 값을 기준으로 내림차순 정렬함

정렬된 데이터에서 S_i를 i번째 행의 튜플에 대해 각 컬럼의 값을 i로 나눈 나머지들의 합으로 정의
row_begin <= i <= row_end 인 모든 S_i를 누적하여 bitwise XOR 한 값을 해시 값으로서 반환함

2. 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int sortIndex;

bool cmp(vector<int> lValue,vector<int> rValue){
    if(lValue[sortIndex]==rValue[sortIndex]) return lValue[0]>rValue[0];
    return lValue[sortIndex]<rValue[sortIndex];
}

int solution(vector<vector<int>> data, int col, int row_begin, int row_end) {
    int answer = 0;
    sortIndex=col-1;
    
    /*for(int i=0;i<data.size();i++){
        for(int j=0;j<data[i].size();j++){
            printf("%d ",data[i][j]);
        }
        printf("\n");
    }*/
    
    sort(data.begin(),data.end(),cmp);
    
    /*printf("\n\n");
    
    for(int i=0;i<data.size();i++){
        for(int j=0;j<data[i].size();j++){
            printf("%d ",data[i][j]);
        }
        printf("\n");
    }*/
    
    int s2;
    for(int i=row_begin-1;i<row_end;i++){
        s2=0;
        for(int j=0;j<data[i].size();j++){
            s2+=data[i][j]%(i+1);
            //printf("%d : %d %d ~~\n",(i+1),data[i][j],data[i][j]%(i+1));
        }
        //printf("%d !!\n",s2);
        answer= answer^s2;
    }
    
    
    return answer;
}

3. 해설

먼저, 테이블의 튜플을 col 번째 컬럼의 값을 기준으로 오름차순 정렬을 합니다

여기서 주의할 점은 col 번재 이기 떄문에 vector의 col-1의 값을 기준으로 정렬해야한다는 점입니다

int solution(vector<vector<int>> data, int col, int row_begin, int row_end) {
    int answer = 0;
    sortIndex=col-1;
    ...
}

bool cmp(vector<int> lValue,vector<int> rValue){
    if(lValue[sortIndex]==rValue[sortIndex]) return lValue[0]>rValue[0];
    return lValue[sortIndex]<rValue[sortIndex];
}

sortIndex라는 변수에 col-1을 할당해주고, algorithm 라이브러리의 sort함수와 제가 정의하는 cmp 비교함수를 이용하여 정렬을 진행했습니다

만약 비교 벡터들의 sortIndex 위치의 값이 같은 경우 기본키를 기준으로 내림차순 정렬을 진행하였습니다

그 후에는 ^ 연산자를 이용하여 XOR 비트 연산을 진행하였습니다

비트연산 XOR 이란?

베타적 OR 연산이라고도 부르는데

두 비트가 서로 다른 경우에만 1이 되고 그렇지 않으면 0이 되는 특이한 연산자

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

row_begin-1 에서 row_end까지 비트연산을 한 값들을 answer에 저장하였습니다

data[i][j]%(i+1)

는 정렬된 데이터에서 S_i를 i번째 행의 튜플(행)에 대해 각 컬럽의 값을 i로 나눈 나머지입니다