[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)입니다.
