[Baekjoon]12782번 비트 우정지수 - Javascript

https://www.acmicpc.net/problem/12782

12782번: 비트 우정지수

문제

진홍이는 숫자를 좋아한다. 오늘도 숫자를 가지고 놀던 진홍이는 두 숫자의 비트 우정지수를 구해보았다. 비트 우정지수란, 10진법으로 나타낸 두 정수를 이진수로 나타내었을 때, 두 숫자를 같게 만드는데 필요한  최소 연산 횟수를 말한다. 연산의 종류는 다음과 같다.

1. 하나의 이진수에서 임의의 자리의 숫자를 0 또는 1로 바꾼다.
2. 하나의 이진수에서 서로 다른 자리에 있는 두 숫자의 위치를 바꾼다.

예를 들어, 10진수 11과 12의 비트 우정지수를 구해보자. 11을 이진수로 나타내면 1011이고, 12를 이진수로 나타내면 1100이다. 1011에서 2의 자리를 0으로 바꾸고(1011 -> 1001), 1의 자리와 4의 자리의 숫자를 서로 바꾸면(1001 -> 1100) 1100이 된다. 즉, 1011을 1100으로 바꾸는 최소 연산 횟수는 두 번으로, 11과 12의 비트 우정지수는 2가 된다.

진홍이는 어떤 두 수가 주어졌을 때 두 수의 비트 우정지수를 구하는 프로그램을 만들고 싶다. 하지만, 아쉽게도 진홍이는 프로그래밍에 약해 10진수를 이진수로 바꾸는 것 밖에 하지 못한다. 여러분이 진홍이를 도와 두 수의 비트 우정지수를 구하는 프로그램을 만들어 주자!

입력

입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 50)가 주어진다.

각 테스트케이스의 첫 번째 줄에는 두 이진수 N, M이 주어진다. N, M의 자릿수는 1,000,000을 넘지 않으며, 자릿수는 서로 같다.

출력

각 테스트 케이스마다 두 수의 비트 우정지수를 출력한다.

예제 입력 1 복사

3
1011 1100
100101 110100
00110100 10010111

예제 출력 1 복사

2
1
3

 

문제풀이(1)

1011, 1100 두개의 2진수 비트 2개가 있을 때, 1011을 1100으로 바꾸는 최소 연산횟수를 구하는 문제이다.
1011 -> 1001 -> 1100으로 바뀐다고 한다.

2개 비트의 1의 개수를 구하면서 서로 자리가 다른 곳의 개수도 구한뒤 계산하면 된다고 생각했다.
2개 비트의 1의 개수가 같을 경우 (자리가 다른 곳의 개수 / 2)를 해주면 1과 0의 위치만 바꾸기 때문에 정답이 나올 것이다.
2개 비트이 1의 개수가 다를 경우 (자리가 다른 곳의 개수 - 첫번째 비트이 1의 개수 - 두번째 비트의 1의 개수) / 2 + (첫번째 비트이 1의 개수 - 두번째 비트의 1의 개수)를 하게되면,
1과 0의 차이만큼 변환을 해주고 자리를 이동하게 되는 로직이다.

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = require("fs").readFileSync(filePath).toString().trim().split("\n");

const N = Number(input.shift());
const bitArr = input.map((el) => el.split(" "));

const answer = [];

for (let i = 0; i < N; i++) {
  const [firstBit, secondBit] = bitArr[i];

  let firstBitOneCount = 0; // 첫번째 비트의 1의 개수
  let secondBitOneCount = 0; // 두번째 비트의 1의 개수
  let differentLocationCount = 0; // 다른 자리수의 개수

  for (let j = 0; j < firstBit.length; j++) {
    if (firstBit[j] === "1") firstBitOneCount++;

    if (secondBit[j] === "1") secondBitOneCount++;

    if (firstBit[j] !== secondBit[j]) differentLocationCount++;
  }

  if (firstBitOneCount === secondBitOneCount) {
    answer.push(Math.floor(differentLocationCount / 2));
  } else {
    let subtract = Math.abs(firstBitOneCount - secondBitOneCount);
    answer.push(Math.floor((differentLocationCount - subtract) / 2 + subtract));
  }
}

console.log(answer.join("\n"));