[solved.ac 실버4] 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을 넘지 않으며, 자릿수는 서로 같다.

출력

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

예제

 

---

나의 풀이

A, B 에 두 숫자를 입력 했다고 했을 때 A를 B로 바꾸는 경우를 생각해보자. (B를 A로 바꾸는 것도 같다)

결론부터 말하면 i번째 숫자를 탐색할 때 A[i]와 B[i]가 다르다면 B[i]가 0일 때와 1일 때 각자 개수를 센 후 더 큰 값이 답이 된다.

예를 들어 A가 '00110100'이고, B가 '10010111'일 때 다음과 같이 나타낼 수 있다.

두 값이 같으면 'x'로, 두 값이 다를 때 B가 1이면 '1'로, 0이면 '0'으로 표시했다.

'x'인 부분은 이미 일치하기 때문에 건들일 필요가 없다.

 

위의 예제처럼 1의 개수가 더 많은 경우를 확인해보자

1의 개수를 ONES, 0의 개수를 ZEROS라고 해보자.

우리는 두 가지 옵션이 있다.

1. 0과 1의 자리를 교환하기
2. 1 -> 0 혹은 0 -> 1

옵션이라고는 했지만 자리를 교환하면 2개 자리를 한 번에 해결할 수 있기 때문에 교환할 수 있는 경우 교환을 하는게 더 이득이다. 1의 개수가 더 많은 경우 최대 0의 개수만큼 교환할 수 있다.

• 교환 횟수 : ZEROS
• 남은 1의 개수: ONES - ZEROS

남은 1의 개수 만큼 이제 2번 옵션을 수행할 수 있다.

그럼 두 이진수를 같게 만드는 작업은 총 (ONES - ZEROS) + (ZEROS) 만큼 수행하게 된다.

ZEROS를 소거하면 ONES가 된다. 결국 1이 더 많을 때 ONES 만큼 수행해야 한다.

 

반대로 0의 개수가 더 많은 경우 ZEROS 만큼 수행하게 될 것이다.

 

결과적으로 ONES와 ZEROS 중 더 큰 값 만큼 수행하게 되는 것이다.

 

정답 코드

for _ in range(int(input())):
    diff0, diff1 = 0, 0
    a, b = input().split()
    for i in range(len(a)):
        if a[i] != b[i]: # 각 자리 수가 다를 때
            if b[i] == '0': # 0 개수 세기
                diff0 += 1
            elif b[i] == '1': # 1 개수 세기
                diff1 += 1
    print(max(diff0, diff1)) # 0과 1 중 더 큰 값

채점 결과