71. Hamming Distance

아현·2021년 5월 22일
0

Algorithm

목록 보기
72/400

리트코드


  • 두 정수를 입력받아 몇 비트가 다른지 계산하라.



1. XOR 풀이


class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        return bin(x ^ y).count('1')
        



  • 해밍 거리(Hamming Distance)

    • 두 정수 또는 두 문자열의 차이를 말한다.

    • 예를 들면, "karolin"과 "kathrin"의 차이는 3이고, 1011101과 1001001의 차이는 2다.

  • 문자열의 경우 해밍 거리는 다른 자리의 문자 개수가 되며, 이진수의 경우 다른 위치의 비트 개수가 된다.


  • 앞서 문제와 같이 동일하게 XOR 연산을 하면, 다른 위치는 1이 될 것이다.

    • 이후 1의 전체 개수를 리터하면 된다.

  • x ^ y XOR의 결과는 정수가 나오므로, 이를 bin()을 이용해 이진수로 변경

    • 여기서 1의 전체 개수를 헤아리면 다른 자리의 개수, 즉 해밍 거리 값이 나온다.





count 함수는 문자열에서 쓰이는 메서드 입니다.

count 함수는 문자열 내부에서 특정 문자, 혹은 문자열이 포함 되어있는지 계산해서 반환해주는 함수 입니다.

.count(self, x, __start, __end)

self는 무시하셔도 좋습니다. 심화적인 부분이라 생각이 들어서

x는 찾을 문자열, 찾을 문자를 넣으면 됩니다.
start, end 는 예상하셨다 싶이 문자열의 어디부터 어디까지 내부에서 찾아달라는 뜻 입니다.

제가 알아본 count의 특징은 이러합니다.

대소문자를 구분합니다.
찾을 x 에 문자 한개를 넣어도 가능하고 문자열을 넣어도 가능합니다.
start, end에 아무것도 넣지 않으면 문자열 처음부터 끝까지 탐색합니다.
찾을 x의 범위는 start <= x < end 입니다. start도 포함 end 는 안 포함.



# 문자열 'BlockDMask' 선언 
a = 'BlockDMask' 

# 문자열에서 'k'가 몇개 있는지 ? 
print('#1 a.count("k")') 
print(a.count('k')) 

# 문자열에서 'DM'가 몇개 있는지 ? 
print('#2 a.count("DM")') 
print(a.count('DM')) 

# 문자열에서 특정 범위 내부에 'k' 가 몇개 있는지? 
# B l o c k D M a s k 에서 index를 표기해보면 
# 0 1 2 3 4 5 6 7 8 9 입니다. 
print("#3 a[2] + ' ~ ' + a[4]") 
print(a[2] + ' ~ ' + a[4]) 

print("#4 a.count('k', 2, 3)") 
print(a.count('k', 2, 3)) 

print("#5 a.count('k', 2, 4)") 
print(a.count('k', 2, 4)) 

print("#6 a.count('k', 2, 5)") 
print(a.count('k', 2, 5))

출처: https://blockdmask.tistory.com/410 [개발자 지망생]

profile
For the sake of someone who studies computer science

0개의 댓글