숫자 리스트가 주어졌을 때, 주어진 모든 숫자 쌍(pair)에 대한 해밍 거리의 합계를 구해야 합니다. 여기서 해밍 거리(Hamming Distance)란 두 정수를 이진수로 표현했을 때, 서로 대응되는 비트 값이 다른 위치의 개수를 의미합니다.
예를 들어 입력이 [4, 14, 17, 2]라면 출력은 17이 됩니다.
문제 해결 접근 방법
모든 쌍을 일일이 비교하면 O(n²)의 시간이 걸리므로 비효율적입니다. 대신 비트 자리별 카운팅 기법을 사용하면 훨씬 효율적으로 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다. 특정 비트 자리에서 0인 숫자가 k개, 1인 숫자가 (n−k)개 있다면, 그 자리에서 서로 다른 비트를 가지는 쌍의 수는 k × (n−k)입니다. 이 값을 32개 비트 자리마다 모두 더하면 전체 해밍 거리를 구할 수 있습니다.
알고리즘 단계
- 모듈러 상수 설정: m := 10⁹ + 7
- add(a, b) 함수 정의: ((a mod m) + (b mod m))을 반환
- mul(a, b) 함수 정의: ((a mod m) × (b mod m))을 반환
- cntBits(a) 함수 정의: 배열 a를 입력으로 받음
- 크기 32×2의 2차원 배열 bits 생성 (bits[j][0]: j번째 비트가 0인 개수, bits[j][1]: 1인 개수)
- ans := 0, n := 배열 a의 크기로 초기화
- i를 0부터 n−1까지 반복:
- x := a[i]
- j를 0부터 31까지 반복:
- b := (x >> j) AND 1 → x의 j번째 비트 추출
- ans := add(ans, mul(1, bits[j][!b])) → 지금까지 등장한 숫자 중 현재 비트와 다른 값을 가진 개수만큼 누적
- bits[j][b] := add(bits[j][b], 1) → 현재 비트 값의 카운트 증가
- ans 반환
- 메인 함수에서는 cntBits(nums)를 호출하여 최종 결과를 반환
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int m = 1e9 + 7;
class Solution {
public:
lli add(lli a, lli b){
return ((a % m) + (b % m));
}
lli mul(lli a, lli b){
return ((a % m) * (b % m));
}
int cntBits(vector<int>& a){
vector<vector<lli> > bits(32, vector<lli>(2));
lli ans = 0;
int n = a.size();
for (int i = 0; i < n; i++) {
lli x = a[i];
for (lli j = 0; j < 32; j++) {
lli b = (x >> j) & 1;
ans = add(ans, mul((lli)1, bits[j][!b]));
bits[j][b] = add(bits[j][b], (lli)1);
}
}
return ans;
}
int totalHammingDistance(vector<int>& nums){
return cntBits(nums);
}
};
main(){
Solution ob;
vector<int> v = {4,14,17,2};
cout << (ob.totalHammingDistance(v));
}입력
{4,14,17,2}출력
17
복잡도 분석
이 알고리즘의 시간 복잡도는 O(n × 32), 즉 O(n)이며, 공간 복잡도는 고정된 크기의 배열만 사용하므로 O(1)입니다. 브루트 포스 방식(O(n²))보다 훨씬 효율적이므로 입력 크기가 클 때도 안정적으로 동작합니다.