알고리즘
[Javascript] 프로그래머스 - 테이블 해시 함수
J3SUNG
2025. 3. 2. 21:46
728x90
문제 설명
주어진 2차원 리스트(테이블)에서 특정 조건에 따라 정렬한 후, 각 행의 값을 이용해 해시 값을 계산하는 문제입니다.
- col번째 컬럼을 기준으로 오름차순 정렬합니다.
- 만약 col번째 컬럼의 값이 같다면, 첫 번째 컬럼의 값을 기준으로 내림차순 정렬합니다.
- row_begin부터 row_end까지의 각 행에 대해 다음 연산을 수행합니다.
- 각 행의 값을 해당 행의 인덱스로 나눈 나머지를 모두 더한 값을 S_i로 정의합니다.
- S_i를 모두 XOR 연산하여 최종 해시 값을 구합니다.
제한 사항
- data의 행 개수는 최대 2,500개입니다.
- 각 행의 열 개수는 최대 500개입니다.
- 각 원소의 값은 1 이상 1,000,000 이하입니다.
- row_begin과 row_end는 유효한 범위 내에서 주어집니다.
해결 방법
알고리즘: 정렬, 누적 합, 비트 연산(XOR)
- 주어진 data를 col-1번째 열을 기준으로 오름차순 정렬합니다.
- 정렬 조건: col번째 값이 같으면 첫 번째 컬럼을 기준으로 내림차순 정렬
- row_begin - 1부터 row_end - 1까지의 각 행을 순회하며 S_i를 계산합니다.
- 각 요소를 해당 행의 인덱스(1부터 시작)로 나눈 나머지의 합을 구합니다.
- S_i 값들을 XOR 연산하여 최종 결과를 도출합니다.
시간 복잡도
- 정렬 연산: O(NlogN)O(N \log N)
- 누적 합 계산: O(NM)O(NM) (각 행에 대해 M개의 원소를 순회)
- 최종 XOR 연산: O(N)O(N)
- 총 시간 복잡도: O(NlogN+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;
}