[Cos Pro 1급] [백준] 1차 2번, 3449번 - 해밍거리

문제

해밍 거리(Hamming distance)란 같은 길이를 가진 두 개의 문자열에서 같은 위치에 있지만 서로 다른 문자의 개수를 뜻 합니다.  예를 들어 두 2진수 문자열이 "10010"과 "110"이라면, 먼저 두 문자열의 자릿수를 맞추기 위해 "110"의 앞에 0 두  개를 채워 "00110"으로 만들어 줍니다. 두 2진수 문자열은 첫 번째와 세 번째 문자가 서로 다르므로 해밍 거리는 2입니다.

 

1 0  0 1 0

0 0  1 1 0

 

두 2진수 문자열 binaryA, binaryB의 해밍 거리를 구하려 합니다.

이를 위해 다음과 같이 간단히 프로그램 구조를 작성했습니다

 

1단계. 길이가 더 긴 2진수 문자열의 길이를 구합니다.

2단계. 첫 번째  2진수 문자열의  길이가  더  짧다면  문자열의   앞에   0을 채워넣어   길이를  맞춰줍니다.

3단계. 두 번째  2진수 문자열의  길이가  더  짧다면  문자열의   앞에   0을 채워넣어   길이를  맞춰줍니다.

4단계. 길이가 같은 두 2진수 문자열의 해밍 거리를 구합니다.

 

두 2진수 문자열 binaryA와 binaryB가 매개변수로 주어질 때,

두 2진수의 해밍 거리를 return 하도록 solution 함수를 작성했습니다.

 

 

매개변수 설명

두 2진수 문자열 binaryA와 binaryB가 solution 함수의 매개변수로 주어집니다.

-binaryA의 길이는 1 이상 10 이하입니다.

-binaryA는 0 또는 1로만 이루어진 문자열이며, 0으로 시작하지 않습니다.

-binaryB의 길이는 1 이상 10 이하입니다.

-binaryB는 0 또는 1로만 이루어진 문자열이며, 0으로 시작하지 않습니다.

 

 

return 값 설명

두 2진수 문자열의 해밍 거리를 return 해주세요.

 

 

 

예시

binaryA	binary	return
"10010"	"110"	2

 

 

Python

def sol(binaryA, binary):
    short, long = "", ""
    if len(binaryA) > len(binary):
        short, long = binary, binaryA
        short = "0"*(len(binaryA)-len(binary)) + short
    else:
        short, long = binaryA, binary
        short = "0"*(len(binary)-len(binaryA)) + short

    distance = 0
    for n, m in zip(short, long):
        if n != m:
            distance+=1

    return distance


binaryA = "10010"
binary = "110"
print(sol(binaryA, binary))

#https://www.acmicpc.net/problem/3449
#NZEC는 Non Zero Exit Code의 약자로 프로그램의 exit code가 0이 아닌 경우를 의미합니다. 많은 프로그램과 운영체제는 정상 종료일때만 0을 리턴합니다.
#import sys
input1,input2 =[], []
for i in range(int(input())):
    input1.append(input())
    input2.append(input())
    
for i in range(len(input1)):
    distance = 0
    for n,m in zip(input1[i], input2[i]):
        if n != m:
            distance+=1

    print("Hamming distance is "+str(distance)+'.')
#sys.exit(1)

 

+) XOR 비트연산자와 Brian Kernighan’s Algorithm 사용 시

#using Brian Kernighan’s Algorithm => O(m)
# m = number of set bits,자릿수
from sys import stdin

def count1(n): 
    if n < 0: 
        raise CustomException('Only accepts non negative numbers') 
 
    distance = 0 
    while (n): 
        n &= (n - 1) 
        distance += 1 
       
    return distance 


for _ in range(int(stdin.readline())):
    b1, b2 = int(stdin.readline(), 2), int(stdin.readline(), 2)
    print("Hamming distance is ",end="")
    print(count1(b1^b2),end='.\n')
    
    #print(bin(a_p1^b_p2).count("1"))   #count() takes O(n) :(