- 원문
The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Given two integers x
and y
, calculate the Hamming distance.
- 해석
두 정수 사이의 해밍 거리는 비트가 다른 위치의 갯수입니다.
두 개의 정수 x와 y가 주어지면, 해밍 거리를 계산하십시오.
Note:
0 ≤ x
, y
< 231.
Example:
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.
public class Solution { private String binaryNotation(int n){ String result = ""; int res; while(n > 0){ res = n % 2; result = res + result; n /= 2; } return result; } public int hammingDistance(int x, int y) { String sx, sy; if(x < y){ int temp = x; x = y; y = temp; } sx = binaryNotation(x); sy = binaryNotation(y); int length = sx.length() - sy.length(); for(int i = 0; i < length; i++){ sy = "0" + sy; } int result = 0; for(int i = 0; i < sy.length(); i++){ if(sx.charAt(i) != sy.charAt(i)){ result++; } } return result; } }
- 회고
난이도에 비해 너무 어렵게 풀었던 것 같다. 10진수를 2진수로 꼭 변경을 해야한다고 생각한 부분이 문제였던 것으로 보인다. 이 문제는 1line 짜리 API를 활용한 해결방안부터 조금 더 Simple한 해결방안이 존재해서 다음을 소개하고자 한다. |
- 1line Solution
public class Solution { public int hammingDistance(int x, int y) { return Integer.bitCount(x ^ y); } }
여기서 bitCount를 JavaAPI를 보면 메서드의 기능은 다음과 같다.
bitCountpublic static int bitCount(int i) 지정된 int 의 2의 보수 바이너리 표현에서의, 1의 비트의 수를 돌려줍니다.
|
그래서 Integer.bitCount에서 bit가 서로 다른 경우 1을 반환하는 XOR연산을 이용해서 bitCount를 사용하는 것으로 쉽게 구할 수 있다.
하지만 API를 이용하지 않고 푸는 것을 면접에서도 원할 수 있기 때문에 찾아보니 다음과 같은 솔루션이 있었다.
- 본인이 생각하기에 최적의 솔루션
public class Solution { public int hammingDistance(int x, int y) { int z = x ^ y; int mask = 1; int count = 0; while(z != 0){ count += z & mask; z >>= 1; } return count; } }
이진수를 구하라는 얘기가 없으면 이진수를 굳이 만드려고 하지말고 비트 연산을 통해서 문제를 해결하도록 하자...
'전공지식 > Leetcode문제' 카테고리의 다른 글
136. Single Number (0) | 2016.12.30 |
---|---|
448. Find All Numbers Disappeared in an Array (0) | 2016.12.30 |
SwapPairs 문제 (0) | 2016.11.22 |