알고리즘

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

J3SUNG 2025. 3. 2. 21:46
728x90

문제 설명

주어진 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(NM)O(NM) (각 행에 대해 M개의 원소를 순회)
  • 최종 XOR 연산: O(N)O(N)
  • 총 시간 복잡도: O(Nlog⁡N+NM)O(N \log N + 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;
}