[BOJ] 비트 우정지수 - JAVA

- 링크 : https://www.acmicpc.net/problem/12782

12782번: 비트 우정지수

 

- 풀이

 - 나는 비트 1 을 기준으로 풀었다.

 - 1. 비트 1을 기준으로 다른 1의 개수를 구한다.

 - 2. 비트 1이 더 많은 글자 기준으로 잡고 같은 1의 글자 개수로 만들어주는데,
  이 때 1의 위치가 두 군데서 모두 같은 숫자는 자리 수를 바꿀 필요가 없으므로
  두 위치에서 다른 글자만 바꿔준다.
  (ex. 1011 1100 -> 101 1 -> 100 1 )

 - 3. 바꿔야 할 횟수를 구한다.

 

- 피드백

  - 다른 분들이 푼 걸 보니 1인데 다른 개수 중 최소값 (위치가 바뀌어야 하는 개수) +  다른 1의 개수 (1이 없어져야할 개수)로 구하는 것이 있었다. 위치를 먼저 바꾸고 1의 개수를 없애주는 형식이다. 멋있는 풀이다.

 

import java.util.Scanner;

public class Solution {

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int t = Integer.parseInt(sc.nextLine());
        for (int i = 0; i < t; i++) {
            String s = sc.nextLine();
            String n = s.split(" ")[0];
            String m = s.split(" ")[1];
            int diffNum = getDiffNumOne(n, m);
            String n1 = getCountNumOne(n) > getCountNumOne(m) ? n : m;
            String m1 = getCountNumOne(n) > getCountNumOne(m) ? m : n;
            n1 = convertDiffNumOne(n1, m1, diffNum);
            int diffPosit = (diffPositNumOne(n1, m1) / 2);
            System.out.println(diffNum + diffPosit);
        }

    }

    private static String convertDiffNumOne(String n, String m, int diffNum) {
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < n.length(); i++) {
            char nc = n.charAt(i);
            char mc = m.charAt(i);
            if (nc == '1' && nc != mc && diffNum > 0) {
                sb.append('0');
                diffNum--;
            } else {
                sb.append(nc);
            }
        }

        return sb.toString();
    }

    public static int getCountNumOne(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            char nc = s.charAt(i);
            if (nc == '1') count++;
        }

        return count;
    }

    public static int getDiffNumOne(String n, String m) {
        int countN = 0;
        int countM = 0;
        for (int i = 0; i < n.length(); i++) {
            char nc = n.charAt(i);
            char mc = m.charAt(i);
            if (nc == '1') countN++;
            if (mc == '1') countM++;
        }

        return Math.abs(countN - countM);
    }

    public static int diffPositNumOne(String n, String m) {
        int count = 0;
        for (int i = 0; i < n.length(); i++) {
            char nc = n.charAt(i);
            char mc = m.charAt(i);
            if (nc != mc) count++;
        }

        return count;
    }
}