[LeetCode] - 461. Hamming Distance

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Hamming Distance" 문제입니다.

--> https://leetcode.com/problems/hamming-distance/description/

 

문제 : 

The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given two integers x and y, return the Hamming distance between them.

---

Example 1 :

Input : x = 1, y = 4

Output : 2

Explanation :

1 (0 0 0 1)

4 (0 1 0 0)

       ↑     ↑

The above arrows point to positions where the corresponding bits are different.

 

Example 2:

Input : x = 3, y = 1

Output : 1

 

Constraints: 0 <= x, y <= 2^31 - 1

---

이 문제는, 해밍 거리(Hamming distance), 즉 두 정수의 이진수 표현에서 서로 다른 비트의 개수를 의미하는데, 이때 두 정수 x와 y가 주어졌을 때, 해밍 거리를 계산하여 반환해야 하는 문제입니다. 위 예시들을 보면 이해가 빠르실 겁니다.

 

1. 재이의 코드 :

class Solution {
    public int hammingDistance(int x, int y) {
        // use XOR to know the difference
        // then count how many 1 there are 
        int hD = 0;
        int res = x ^ y;
        String resBin = "";
        
        if (res == 0) {
            resBin += "0";
        } else { 
            while (res > 0) {
                int remainder = res % 2;
                resBin += remainder;
                res /= 2;
            }
        }
        for (int i = 0; i < resBin.length(); i++) {
            if (resBin.charAt(i) == '1') {
                hD++;
            }
        }
        return hD;
    }
}

 

제 코드는 보시다시피 아주 효율적이진 못합니다. 그래서 이 이후에는 다른 유저들의 답안들 중 하나를 보여드릴 겁니다. 그래도 제가 어떤 생각으로 이 코드를 썼는지는 3단계로 간단히 설명해 보겠습니다 : 

 

• 1. XOR 연산:
  • int res = x ^ y;
  • XOR 연산은 두 숫자의 각 비트가 다른 경우에만 1을 반환합니다. 따라서 x와 y의 XOR 결과는 비트가 다른 위치를 1로 표시한 이 진수입니다.
• 2. 이진수 변환:
  • String resBin = "";
  • if (res == 0) { resBin += "0"; } else { ... }
  • res 값을 이진수 문자열로 변환합니다.
  • res가 0인 경우, 이진수 문자열은 "0"입니다.
  • res가 0이 아닌 경우, while 루프를 사용하여 2로 나눈 나머지를 구하고 이를 resBin에 추가합니다. 그리고 res를 2로 나눕니다.
• 3. 해밍 거리 계산:
  • for (int i = 0; i < resBin.length(); i++) { ... }
  • 이진수 문자열 resBin을 순회하면서 '1'의 개수를 셉니다.
  • '1'의 개수가 해밍 거리가 됩니다.

 

제 코드는 문자열에 이진수를 추가하는 과정에서 문자열 연결(+=) 연산이 이루어지는데, 이는 각 단계에서 새 문자열을 생성하기 때문에 시간 복잡도가 O(log N)이 아니라 O((log N)^2)가 될 수 있습니다. 각 += 연산은 새로운 문자열을 생성하므로 추가적인 시간 복잡도를 가집니다 그래서 다른 이들의 코드보다 더 느리고 비효율적이라고 생각됩니다 

---

2. 다른 유저의 모범답안 : 

class Solution {
    public int hammingDistance(int x, int y) {
        int ans=x^y;
        int c=0;
        while(ans!=0){
            ans = ans & (ans-1);
            c++;
        }
        return c;
        
    }
}
// iamsubrat1유저의 코드

 

위 코드는 결국 저랑 비슷한 아이디어지만, 더 효율적이고 빠른 코드입니다. 간략한 설명을 덧붙이자면 :

• XOR 연산을 통해 두 숫자의 서로 다른 비트 위치를 찾아냅니다.
• 반복문을 통해 가장 오른쪽에 있는 1을 하나씩 제거하면서 카운터를 증가시킵니다.
• 최종적으로 카운터 c는 해밍 거리, 즉 서로 다른 비트의 개수를 반환합니다.

 

시간 복잡도는 O(k)입니다. 여기서 k는 ans의 이진수 표현에서 1의 개수입니다. 일반적으로 k는 정수의 비트 수인

O(log N)보다 작거나 같으므로, 최악의 경우 시간 복잡도는 O(log N)입니다.

---

 

 

1,2 코드들의 Runtime 결과