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

테이블 해시 함수

문제 링크

테이블 해시 함수

분석

문제에서 튜플(tuple)이라는 단어가 나오는데 데이터의 행 원소들의 집합을 의미합니다.
mod는 나머지 연산을 의미합니다.
XOR은 비트 연산자 중 같은 자릿수의 비트가 서로 다를 경우 1, 같을 경우 0을 출력하는 연산자입니다.

row_begin과 row_end는 정렬된 데이터 기준으로 어떤 범위의 행에 연산을 적용할지를 나타냅니다.
예를 들어, row_begin = 2, row_end = 4인 경우, 정렬된 데이터의 2번째, 3번째, 4번째 행에 연산을 적용한다는 의미입니다.

S_i는 정렬된 데이터에서 i번째 행의 각 열 원소들을 원소 mod i로 값을 구하고 누적한 값입니다.
즉, row_begin부터 row_end까지의 행에서 원소들을 원소 % i로 값을 구하고 모두 더한 값입니다.
예를 들어, 문제의 입출력 예에서 i = 2인 경우, S_2 = (2 % 2) + (2 % 2) = 0 + 0 = 0입니다.
i = 3인 경우, S_3 = (1 % 3) + (4 % 3) = 1 + 1 = 2입니다.

풀이

#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> data, int col, int row_begin, int row_end) {
    int answer = 0;
    
    // 사용자 정의 정렬
    // col은 1-based로 주어지므로 0-based로 조정
    sort(data.begin(), data.end(), [col](const vector<int>& v1, const vector<int>& v2)
    {
        // 기준 열 값이 동일한 경우 첫 번째 열 값을 기준으로 내림차순 정렬합니다.
        if (v1[col - 1] == v2[col - 1])
        {
            return v1[0] > v2[0]; // 첫 번째 열 값 기준 내림차순
        }
        
        // 기준 열 값으로 오름차순 정렬합니다.
        return v1[col - 1] < v2[col - 1]; // 오름차순
    });
    
    // 정렬된 데이터에서 S_i 계산 및 XOR 누적
    // row_begin과 row_end은 1-based로 주어지므로 0-based로 조정
    for (int i = row_begin - 1; i <= row_end - 1; ++i)
    {
        int S_i = 0;
        for (int number : data[i])
        {
            // 현재 i는 0-based이므로, 1-based로 맞추기 위해 i + 1으로 조정
            S_i += number % (i + 1);
        }
        
        // XOR 연산 누적
        answer ^= S_i;
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(n \ log \ n) + O(n \times m)$입니다.

• sort함수 $O(n \ log \ n)$
• row_begin부터 row_end까지 S_i를 구하는 반복문 $O(n \times m)$
• $O(n \ log \ n) + O(n \times m)$

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

테스트 1 〉 통과 (0.01ms, 4.2MB)
테스트 2 〉 통과 (0.02ms, 4.14MB)
테스트 3 〉 통과 (0.02ms, 4.14MB)
테스트 4 〉 통과 (0.03ms, 4.03MB)
테스트 5 〉 통과 (0.30ms, 6MB)
테스트 6 〉 통과 (4.87ms, 54.9MB)
테스트 7 〉 통과 (4.88ms, 57.6MB)
테스트 8 〉 통과 (5.63ms, 57.4MB)
테스트 9 〉 통과 (6.04ms, 57.4MB)
테스트 10 〉 통과 (6.20ms, 57.3MB)
테스트 11 〉 통과 (0.01ms, 4.21MB)
테스트 12 〉 통과 (0.01ms, 4.15MB)
테스트 13 〉 통과 (0.01ms, 4.13MB)
테스트 14 〉 통과 (0.01ms, 3.68MB)
테스트 15 〉 통과 (0.01ms, 4.13MB)
테스트 16 〉 통과 (0.01ms, 4.14MB)
테스트 17 〉 통과 (0.01ms, 4.21MB)