[프로그래머스] Level 2 : 테이블 해시 함수

https://school.programmers.co.kr/learn/courses/30/lessons/147354

프로그래머스

 

문제 설명이 굉장히 난해하지만, 그냥 문제 설명 그대로를 구현해 주면 문제없이 풀린다.

 

먼저, 테이블 튜플을 정렬해줘야 한다.

이는 그냥 문제의 정렬 기준으로 테이블 배열을 정렬해주면 된다.

파라미터로 주어지는 col값은 인덱스 순서인 0부터 시작하는게 아닌, 1부터 시작하기 때문에 -1을 해줘야 한다.

나는 정렬 함수를 따로 만들어 사용했기 떄문에, 전역 변수 col을 하나 더 선언 후에 col-1로 초기화했다.

 

다음으로, 각 칼럼의 값을 i로 나눈 나머지들의 합 구해야 한다.

여기 문제 설명이 굉장히 난해하게 되어있지만, 결국에는 그냥 각 행을 모두 i로 나눈 나머지를 더해주면 된다.

 

다음으로 row_begin부터 row_end까지 누적해서 xor 하기이다.

앞서 구한 나머지들의 합 배열을 row_begin부터 row_end까지 누적 xor 해주면 된다.

이도 마찬가지로 인덱스 순서가 아니므로 answer을 row_begin -1로 초기화해주고 여기다가 누적 xor를 해줬다.

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

// 기준 컬럼의 값을 인덱스로 변환하기 위해서 전역 변수로 선언
int Col;

struct cmp
{
	bool operator()(vector<int>& a, vector<int>& b)
	{
		// 값이 동일하면 기본키인 첫 번째 컬럼의 값을 기준으로 내림차순 정렬
		if (a[Col] == b[Col]) return a[0] > b[0];

		// col번째 컬럼의 값을 기준으로 오름차순 정렬
		return a[Col] < b[Col];
	}
};

int solution(vector<vector<int>> data, int col, int row_begin, int row_end)
{
	// 기준 컬럼의 값을 인덱스로 변환하여 저장
	Col = col - 1;

	// 2. 테이블 튜플 정렬
	sort(data.begin(), data.end(), cmp());

	// 3. 각 컬럼의 값을 i 로 나눈 나머지들의 합 구하기
	// 설명이 난해하지만, 결국에는 각 컬럼의 값을 i로 나눈 나머지들의 합을 저장하는 것이다.
	vector<int> S(data.size());
	for (int i = 0; i < data.size(); ++i)
	{
		for (int j = 0; j < data[i].size(); ++j)
		{
			S[i] += data[i][j] % (i + 1);
		}
	}

	// 4. row_begin부터 row_end까지 누적해서 xor하기
	// 인덱스 범위는 [row_begin -1 ~ row_end-1]이다.
	// 누적합을 계산해야 하기 때문에, answer을 row_begin -1로 초기화 후, 반복문으로 계속 누적 xor을 한다.
	int answer = S[row_begin - 1];
	for (row_begin; row_begin < row_end; ++row_begin)
	{
		answer ^= S[row_begin];
	}

	return answer;
}