[백준,c++] 12782번 - 비트 우정지수

문제

12782번: 비트 우정지수

 

코드

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int T; cin>>T;
    while(T--){
        string a, b; cin>>a>>b;
        queue<int> zero, one;
        int ans = 0;
        
        for(int i=0; i<a.length(); i++){
            if(a[i] != b[i]){
                if(a[i] == '0') zero.push(i);
                else if(a[i] == '1') one.push(i);
            }
        }
        int len = min(zero.size(), one.size());
        
        while(len--){   // 하나의 이진수에서 서로 다른 자리에 있는 두 숫자의 위치를 바꾼다.
            swap(a[zero.front()], a[one.front()]);
            zero.pop();
            one.pop();
            ans++;
        }
        for(int i=0; i<a.length(); i++){    // 하나의 이진수에서 임의의 자리의 숫자를 0 또는 1로 바꾼다.
            if(a[i] != b[i]) ans++;
        }
        cout<<ans<<'\n';
    }
    
}

 

풀이

A비트와 B비트가 주어졌을 때 A비트를 B 비트로 아래의 두 연산을 가지고 만들 수 있는 최소 연산 횟수를 구하는 문제입니다.

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

2번 연산을 최대한 사용해야 최소 연산 횟수를 만들 수 있습니다. 따라서 풀이 아이디어는 2번 연산을 최대한 사용한 후 1번 연산을 이용하면 됩니다.

00110100 10010111

위와 같은 예시를 가지고 정리해 보겠습니다.

먼저 2번 연산을 최대한 사용하기 위해서 A비트와 B비트의 인덱스를 비교해 가면서 비트가 다를 경우 0 숫자와 1 숫자 각각의 위치를 아래와 같이 저장합니다.

• zero = [0, 6, 7]
• one = [2]

그 후, 둘 중 작은 사이즈의 크기만큼 반복하면서 0의 위치와 1의 위치를 변경합니다. 위의 경우 00110100의 0번째 인덱스와 2번째 인덱스를 변경합니다.

그 후 , 1번 연산을 위해  A비트와 B비트의 인덱스를 비교해 가면서 비트가 다를 경우 0 또는 1로 바꾸는 작업을 수행하면 됩니다.