COS PRO 1급 C) 해밍 거리 구하기

해밍 거리란 같은 길이를 가진 2개의 문자열에서 같은 위치에 있지만 서로 다른 문자의 개수를 뜻한다.

 

예) 두 2진수 문자열이 "10010"과 "110"이라면, 먼저 두 문자열의 자릿수를 맞추기 위해 "110" 옆에 0 두개를 채워 "00110"으로 만들어 준다.

1 0 0 1 0

0 0 1 1 0

두 문자열은 첫 번째와 세 번째 문자가 서로 다르므로 해밍 거리는 2이다.

 

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

1. 길이가 더 긴 2진수 문자열의 길이를 구한다.
2. 첫 번째 2진수 문자열의 길이가 더 짧다면 문자열의 앞에 0을 채워넣어 길이를 맞춰준다.
3. 두 번째 2진수 문자열의 길이가 더 짧다면 문자열의 앞에 0을 채워넣어 길이를 맞춰준다.
4. 길이가 같은 두 2진수 문자열의 해밍 거리를 구한다.

 

---

▼ strcat 함수란?
함수 원형 : char* strcat(char* dest, const char* origin);

1) origin에 있는 문자열을 dest 뒤쪽에 이어 붙이는 함수 입니다.
2) dest 문자열 끝에 있는 '\0' 이것은 사라지고 그 위치에 origin이 바로 붙어버리는게 특징입니다.
3) strcat 간단한 사용법 
char origin[] = "BlockDMask";
char dest[20] = "aaabbb";
strcat(dest, origin);

결과 : "aaabbbBlockDMask";

출처: 
https://blockdmask.tistory.com/350

---

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

char* func_a(char* str, int len){
    char* padZero = (char*)malloc(sizeof(char)*(len+1));
    for(int i = 0; i < len+1; ++i)
        padZero[i] = 0;
    
    int padSize = len - strlen(str);
    
    for(int i = 0; i < padSize; ++i)
        padZero[i] = '0';
    
    strcat(padZero, str);
    
    return padZero;
}

int max(int a, int b){
    return a > b ? a : b;
}

int solution(char* binaryA, char* binaryB) {
    int max_length = max(strlen(binaryA), strlen(binaryB));
    
    if(max_length > strlen(binaryA))
        binaryA = func_a(binaryA, max_length);
    
    if(max_length > strlen(binaryB))
        binaryB = func_a(binaryB, max_length);
    
    int hamming_distance = 0;
    
    for(int i = 0; i < max_length; ++i)
        if(binaryA[i] != binaryB[i])
            hamming_distance += 1;
    
    return hamming_distance;
}

 

strlen에 대하여

size_t strlen(const char* str);

const char* 타입의 문자열을 받아서 해당 문자열의 길이를 반환하는 함수입니다.
반환 할때 보이는 size_t 타입은 객체나 값이 포함 할수 있는 최대 크기의 데이터를 표현하는 데이터 타입 입니다.

strlen 함수는 C언어 스타일의 문자열을 받아서 그것의 길이를 반환하는 함수인데요.
C언어 스타일의 문자열. 즉 char* str = "BlockDMask"이 문자열의 끝에는 문자열의 끝을 알려주는 '\0' 문자가 포함 되어있는거 다들 아시죠?

strlen 함수의 원리는 char*가 가리키는 주소에서 부터 시작해서 '\0'이 문자가 나올때까지의 문자들의 개수를 이태리 장인처럼 하나하나 세서 최종 길이를 반환하는 그런 원리 입니다.
그렇기 때문에 문자열 중간에 '\0' 값을 슉 넣어버리면  strlen이 '\0'이걸 인지하고 그 길이 까지만 반환을 하게 됩니다.

▶ 간단예제
1. const char* 을 넘길때
const char* name = "BlockDMask";
strlen(name);    //strlen의 반환값 : 10
 
2. char 배열을 넘길때
char arr[50] = "BlockDMask";
strlen(arr);        //strlen의 반환값 : 10

3. 문자열 중간에 '\0'가 있을때
char arr[50] = "Block\0DMask";
strlen(arr);        //strlen의 반환값 : 5

출처: 
https://blockdmask.tistory.com/381