[백준 / BOJ 12782] 비트 우정지수

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을 넘지 않으며, 자릿수는 서로 같다.

출력

---

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

 

 

풀이

---

bit_1	1	0	1	1
bit_2	1	1	0	0

두 수의 각 비트들을 비교하면서 다를 때, bit_1의 1의 갯수(cntOne)와 0의 갯수(cntZero)를 따로 저장했다. cntOne과 cntZero 중 더 작은 값 만큼 교환해주고 나머지는 반대값으로 바꾸어주면 간단하게 값을 찾을 수 있다. 

위 예시에서는 cntOne은 2, cntZero는 1이다. 더 작은 값은 1이므로 1번 1과 0을 교환해준다. 그리고 cntOne - cntZero 번 1을 0으로 바꾸어 주었다.

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_BOJ_12782_비트우정지수 {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer stringTokenizer;

        int testCase = Integer.parseInt(br.readLine());

        while(testCase-- > 0){
            stringTokenizer = new StringTokenizer(br.readLine());

            char[] bit1 = stringTokenizer.nextToken().toCharArray();
            char[] bit2 = stringTokenizer.nextToken().toCharArray();

            int cntOne = 0;
            int cntZero = 0;
            for(int i = 0; i < bit1.length; i++){
                if(bit1[i] != bit2[i]){
                    if(bit1[i] == '1')
                        cntOne++;
                    else
                        cntZero++;
                }
            }

            if(cntZero < cntOne){
                sb.append(cntZero + (cntOne - cntZero)).append("\n");
            }
            else if(cntOne < cntZero){
                sb.append(cntOne + (cntZero - cntOne)).append("\n");
            }
            else{
                sb.append(cntOne).append("\n");
            }
        }

        System.out.print(sb);
    }
    
}