[Javascript] 프로그래머스 - 테이블 해시 함수

문제 설명

주어진 2차원 리스트(테이블)에서 특정 조건에 따라 정렬한 후, 각 행의 값을 이용해 해시 값을 계산하는 문제입니다.

1. col번째 컬럼을 기준으로 오름차순 정렬합니다.
2. 만약 col번째 컬럼의 값이 같다면, 첫 번째 컬럼의 값을 기준으로 내림차순 정렬합니다.
3. row_begin부터 row_end까지의 각 행에 대해 다음 연산을 수행합니다.
   • 각 행의 값을 해당 행의 인덱스로 나눈 나머지를 모두 더한 값을 S_i로 정의합니다.
   • S_i를 모두 XOR 연산하여 최종 해시 값을 구합니다.

---

제한 사항

• data의 행 개수는 최대 2,500개입니다.
• 각 행의 열 개수는 최대 500개입니다.
• 각 원소의 값은 1 이상 1,000,000 이하입니다.
• row_begin과 row_end는 유효한 범위 내에서 주어집니다.

---

해결 방법

알고리즘: 정렬, 누적 합, 비트 연산(XOR)

1. 주어진 data를 col-1번째 열을 기준으로 오름차순 정렬합니다.
   • 정렬 조건: col번째 값이 같으면 첫 번째 컬럼을 기준으로 내림차순 정렬
2. row_begin - 1부터 row_end - 1까지의 각 행을 순회하며 S_i를 계산합니다.
   • 각 요소를 해당 행의 인덱스(1부터 시작)로 나눈 나머지의 합을 구합니다.
3. S_i 값들을 XOR 연산하여 최종 결과를 도출합니다.

---

시간 복잡도

• 정렬 연산: O(Nlog⁡N)O(N \log N)O(NlogN)
• 누적 합 계산: O(NM)O(NM)O(NM) (각 행에 대해 M개의 원소를 순회)
• 최종 XOR 연산: O(N)O(N)O(N)
• 총 시간 복잡도: O(Nlog⁡N+NM)O(N \log N + NM)O(NlogN+NM)

---

구현 코드

function solution(data, col, row_begin, row_end) {
    let answer = 0;

    data.sort((a, b) => a[col - 1] - b[col - 1] || b[0] - a[0]);

    for (let i = row_begin - 1; i < row_end; ++i) {
        let num = data[i].reduce((sum, item) => sum + (item % (i + 1)), 0);
        answer ^= num; 
    }

    return answer;
}