BOJ) 비트 우정지수

비트 우정지수

12782번: 비트 우정지수

풀이

 

문제를 풀 방법에 대해 고민에 조금 시간을 들였다. 두 수의 2진수 비트를 갖게 만드는 방법이기 때문에, 하나씩 바꿔나가는 과정이 비합리적이라고 생각이 들었다. 그래서 방법을 고민하다가, 위치가 다른 포지션의 수와 1의 갯수 차이를 통해 풀 수 있지 않을까 하는 생각이 들었다.

 

좌측과 우측의 2진수 비트에 대해 1의 수를 각각 카운트 해주었고, 서로 다른 포지션인 경우를 담는 변수도 카운트를 진행해주었다.

진행이 끝난 이후에 1의 갯수가 같다면, 위치 이동만 하면 되기 때문에, diff/2를 바로 출력해주었다.( 만약 1과 3의 위치가 다르다면 2개가 카운트 되기 때문에 /2를 해주었다.)

 

1의 갯수가 다르다면, 그만큼 1을 늘려주거나 지워줘야하기 때문에 차이가 나는 갯수만큼 변환 횟수에 들어가게 된다.

또한 포지션이 다른 갯수에서 변환한 수 만큼 빼주어야 한다. (포지션이 달랐던 부분이 변환 후에 같아지기 때문에)

이후 diff에는 이제 포지션이 다른 경우만 남았다. 변환 횟수와 diff/2를 통해 변경 횟수를 구해준다.

 

정확한 포지션 위치에 따라 연산을 하지 않는 이유는 최소로 움직이는 경우의 수기 때문이다.

위와 같이 진행할 경우에 이미 같은 포지션은 건드리지 않고, 다른 포지션에 대해서만 진행한다고 생각하면 편할 것 같다.

이러한 수식이 가능한 이유는, 움직이는 칸의 수가 아니기 때문에 가능하다.

 

로직

1. 좌우의 2진수 비트를 비교하면서 다른 경우에 카운트를 세준다. 동시에 left와 right의 1의 갯수를 각각 카운트해준다.

2. left와 right가 1의 갯수가 같은 경우는 이동만 하면 최소 움직임을 보여주기 때문에, diff/2를 출력해준다.

3. 1의 갯수가 다른 경우에는, 차이가 나는 만큼 0->1 또는 1->0으로 변환해주어야 하기때문에 변환해야하는 횟수만큼 diff에서 빼준다. 

4. 3의 과정을 마치면 이동만 남았기 때문에 diff/2로 이동 횟수를 구해준다. 또한, 3에서 변환했던 갯수 만큼 더해준다.

 

 

코드

 

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

public class BitFriendShip_12782 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int len = Integer.parseInt(br.readLine());
        String[] caseArr = new String[len];
        for(int i=0; i<len; i++) {
            caseArr[i] = br.readLine();
        }

        solution(caseArr);

        br.close();
    }

    private static void solution(String[] caseArr) {
        for(String str : caseArr) {
            char[] left = str.split(" ")[0].toCharArray();
            char[] right = str.split(" ")[1].toCharArray();

            int leftCnt =0;
            int rightCnt =0;
            int diff =0;
            for(int i=0; i<left.length; i++) {
                if(left[i] =='1') {
                    leftCnt++;
                }
                if(right[i] =='1') {
                    rightCnt++;
                }
                if(left[i] != right[i]) {
                    diff++;
                }
            }

            if(leftCnt == rightCnt) {
                System.out.println(diff/2);
            } else {
                int change = Math.abs(leftCnt-rightCnt);
                System.out.println(((diff-change)/2+ change));
            }
        }
    }
}