[프로그래머스] 테이블 해시 함수(C++)

테이블 해시 함수 147354

🌋 문제 설명

---

완호가 관리하는 어떤 데이터베이스의 한 테이블은 모두 정수 타입인 컬럼들로 이루어져 있습니다. 
테이블은 2차원 행렬로 표현할 수 있으며 열은 컬럼을 나타내고, 행은 튜플을 나타냅니다.
첫 번째 컬럼은 기본키로서 모든 튜플에 대해 그 값이 중복되지 않도록 보장됩니다. 
완호는 이 테이블에 대한 해시 함수를 다음과 같이 정의하였습니다.

1. 해시 함수는 col, row_begin, row_end을 입력으로 받습니다.

2. 테이블의 튜플을 col번째 컬럼의 값을 기준으로 오름차순 정렬을 하되, 만약 그 값이 동일하면 기본키인 첫 번째 컬럼의 값을 기준으로 내림차순 정렬합니다.

3. 정렬된 데이터에서 S_i를 i 번째 행의 튜플에 대해 각 컬럼의 값을 i 로 나눈 나머지들의 합으로 정의합니다.

4. 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의 길이

🛳 풀이

---

만약 라이브러리를 잘 알고있었다면 정말 풀기 쉬웠을 것 같다.
이 문제의 관건은 3가지였다.

1. 원하는대로 sort 를 구현할 수 있는가.
2. 2진수와 10진수 변환에 익숙한가.
3. XOR 비트연산자를 알고 있었는가.

개인적으로 3번을 제외하면 (이게 가장 중요한 것이지만) 어느정도 구현할 수 있었다.

1. 원하는대로 sort 를 구현할 수 있는가.
이 부분은 sort 를 사용하면서도 compare 함수를 구현할 수 있어야 한다.
평소 정렬 방법은 제대로 C++ 로 구현할 수 있었기 때문에 무리가 없었다. << Python 도 익숙해질 필요가 있다.

2. 2진수와 10진수 변환에 익숙한가.
라이브러리가 아닌 . . 직접 계산으로 구할 수 있다.
하지만 구글링을 통해 bitset 이라는 라이브러리를 발견. . .!
10진수 int 를 쉽게 bitset 형으로 변환해서 2진수로 바꿀 수 있다.

이때 제한사항에서 1 < data[i][j] <= 1,000,000 이라고 나타나 있었기 때문에 bitset<20> 으로 만들어 주었다.

3. XOR 비트연산자를 알고 있었는가.
정확히 말하면 X 이다. .
비트에 많이 약했던 탓에 , , , ㅠ . ㅠ

^ 연산자를 쓰면 XOR 연산이 가능하다는 것을 보고 bitset 을 활용하여 구해주었다.
또한 이때 to_ulong() 을 활용하면 2진수 -> 10진수 변환도 가능하니까 잘 알아두면 C++ 로 2진수 <-> 10진수 변환이 쉬워질 것 같다.

🏀 코드

#include <string>
#include <vector>
#include <bitset>
#include <iostream>
#include <algorithm>
using namespace std;

int col_idx;

bool compare(vector<int> a, vector<int> b) {
    if (a[col_idx - 1] < b[col_idx - 1]) return true;
    else {
        if (a[col_idx - 1] == b[col_idx - 1]) {
            if (a[0] > b[0]) return true;
            else return false;
        }
        else return false;
    }
}

int solution(vector<vector<int>> data, int col, int row_begin, int row_end) {
    int answer = 0;
    vector<int> answer_lst;
    
    col_idx = col;
    
    sort(data.begin(), data.end(), compare);
    
    for (int i = row_begin - 1; i < row_end; i++) {
        int tmp = 0;
        for (int j = 0; j < data[0].size(); j++) tmp += (data[i][j] % (i + 1));
        answer_lst.push_back(tmp);
    }
    
    bitset<20> num1(answer_lst[0]);
    for (int i = 1; i < answer_lst.size(); i++) {
        bitset<20> num2(answer_lst[i]);
        
        num1 = bitset<20>(num1 ^ num2);
    }
    
    answer = num1.to_ulong();
    return answer;
}

👖 어려웠던 점

• 비트연산자 에 대해서 조금 더 확실하게 알아 둘 필요가 있다. . .
  • 보통 AND, OR 가 익숙해서 다른 연산자는 좀 낯선데 이런 문제가 실제로 나온다면 당황할 것 같음 ㅠ . ㅠ