BOJ 3449 - 해밍 거리

문제

같은 길이의 두 이진 문자열에서 서로 다른 비트의 개수(해밍 거리)를 구하라.

입력

첫째 줄에 테스트 케이스 수 T, 이후 두 줄씩 이진 문자열 쌍이 주어진다.

출력

각 테스트 케이스마다 "Hamming distance is X."를 출력한다.

예제

입력	출력
`1` `0` `1`	`Hamming distance is 1.`

풀이

두 문자열을 같은 인덱스에서 비교하여 다른 문자의 수를 센다.

두 문자열을 입력받는다
같은 인덱스의 문자를 비교하여 다른 경우 카운트를 증가시킨다
결과를 지정된 형식으로 출력한다

핵심 아이디어: 해밍 거리는 같은 위치에서 다른 비트의 수이므로, 단순 문자 비교로 O(L)에 구할 수 있다.

코드

#include <iostream>
using namespace std;
 
int main()
{
  string num1;
  string num2;
  int t;
  cin >> t;
 
  for (int i = 0; i < t; i++)
  {
    cin >> num1 >> num2;
    int cnt = 0;
    for (int j = 0; j < num1.length(); j++)
    {
      if (num1[j] != num2[j])
        cnt++;
    }
    cout << "Hamming distance is " << cnt << "." << endl;
  }
}

복잡도

시간: O(T * L) (L: 문자열 길이)
공간: O(L)

문제