1. 관련 문제 🎯
문제 : 프로그래머스 테이블 해시 함수 #️⃣
난이도 : LEVEL 2
2. 문제 소개 🧩
[첫번째 칼럼, 두번째 칼럼, ... col번째 컬럼, ...]
1️⃣ 첫 번째 컬럼은 기본키로서 모든 튜플에 대해 그 값이 중복되지 않도록 보장된다.
완호는 이 테이블에 대한 해시 함수를 다음과 같이 정의하였습니다.
해시 함수는 col, row_begin, row_end을 입력으로 받습니다.
1️⃣ 테이블의 튜플을 col번째 컬럼의 값을 기준으로 오름차순 정렬을 하되, 만약 그 값이 동일하면 기본키인 첫 번째 컬럼의 값을 기준으로 내림차순 정렬한다.
2️⃣ 정렬된 데이터에서 S_i를 i 번째 행의 튜플에 대해 각 컬럼의 값을 i 로 나눈 나머지들의 합으로 정의한다.
3️⃣ row_begin ≤ i ≤ row_end 인 모든 S_i를 누적하여 bitwise XOR 한 값을 해시 값으로서 반환한다.
3. 문제 풀이 🖌️
위의 예시를 통해서 더 자세하게 문제를 생각해보자🤔
과정 1️⃣
col번째 열의 값을 기준으로 오름차순 정렬하고, col번째 열의 값이 동일하다면 1번째 열의 값을 기준으로 내림차순 정렬한다.
여기에서 col의 값은 2이므로 2번째 열의 값을 기준으로 오름차순 정렬해보자!
2번째 열의 값을 오름차순으로 정렬해보면 {2,2,5,8}이다.
☝️ 이때, 2와 2의 값이 동일하므로 해당 값을 가진 행을 살펴보면 [2,2,6]과 [4,2,9]이다.
그러면 1번째 열의 값을 기준으로 내림차순해보면 2가 4보다 작으므로 [4,2,9], [2,2,6] 순서가 된다.
따라서 최종적으로 정렬된 값은 [4,2,9], [2,2,6], [1,5,10], [3,8,3]이다!
과정 2️⃣
정렬된 리스트를 바탕으로 row_begin번째 행부터 row_end번째 행까지 S_i를 구한다.
이때, S_i는 S_i = 1번째 행의 값 mod i + 2번째 행의 값 mod i + … + n번째 행의 값 mod i이며, i는 행의 번호를 의미한다.
과정 3️⃣
row_begin ≤ i ≤ row_end 인 모든 S_i를 누적하여 bitwise XOR 한 값을 해시 값으로서 반환한다.
여기에서 row_begin은 2이고, row_end는 3이므로 2번째 행과 3번째 행의 S_i를 구한다.
1️⃣ 2번째 행 [2,2,6] : S_2 = 2 % 2 + 2 % 2 + 6 % 2 = 0 + 0 + 0 = 0
2️⃣ 3번째 행 [1,5,10] : S_3 = 1 % 3 + 5 % 3 + 10 % 3 = 1 + 2 + 1 = 4
따라서 S_2과 S_3을 XOR한 값인 0 XOR 4 = 4이다!
4. 전체 코드 🔑
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int k = 0;
//col번째 열의 값을 기준으로 오름차순 정렬하고
//col번째 열의 값이 동일하다면 1번째 열의 값을 기준으로 내림차순 정렬한다.
bool compare(vector<int> a, vector<int> b){
if(a[k]==b[k]) return a[0] > b[0];
return a[k] < b[k];
}
int solution(vector<vector<int>> data, int col, int row_begin, int row_end) {
k = col-1;
sort(data.begin(), data.end(), compare); //정렬하기
int result_sum = 0;
//정렬된 리스트를 바탕으로 row_begin번째 행부터 row_end번째 행까지 S_i를 구한다.
for(int i=row_begin-1; i<row_end; i++){
int result = 0;
for(int j=0; j<data[0].size(); j++){
result += data[i][j] % (i+1);
}
//모든 S_i를 누적하여 bitwise XOR 한 값을 해시 값으로서 반환한다.
result_sum = result_sum ^ result;
}
return result_sum;
}☝️ 이때, 가장 중요한 점은 원하는 기준으로 정렬하기 위해서 compare과 같이 함수를 정의한다는 점이다!!
return a[k] < b[k]와 같이 <를 사용한 경우 오름차순으로 정렬되며,
return a[0] > b[0]와 같이 >를 사용한 경우 내림차순으로 정렬된다.
📚참고 자료(sort 사용법 및 compare 함수 관련) : https://leeeegun.tistory.com/5
5. 결과 🏆
