백준 12782번 [비트 우정지수](C++) -yes6686- 티스토리

백준 문제 풀이: 12782 [비트 우정지수]

---

문제 링크: https://www.acmicpc.net/problem/12782

문제 설명:

두 이진수 문자열 s1과 s2가 주어졌을 때, s1을 s2로 바꾸기 위해 필요한 최소 연산 횟수를 구하는 문제입니다. 연산은 다음과 같이 정의됩니다:

1. 1을 0으로 바꾸기
2. 0을 1로 바꾸기

각 비트를 비교하여 서로 다른 비트를 최소 횟수로 맞추는 과정을 계산합니다.

---

문제 해결 코드

// 백준 12782 - 비트 우정지수
#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T; // 테스트 케이스 개수

    while (T--) {
        string s1, s2;
        cin >> s1 >> s2; // 두 이진수 입력

        int cnt0 = 0, cnt1 = 0; // s1[i] != s2[i]인 경우의 개수
        for (int i = 0; i < s1.size(); i++) {
            if (s1[i] != s2[i]) {
                if (s1[i] == '0') cnt0++; // s1의 0을 1로 변경해야 함
                else cnt1++; // s1의 1을 0으로 변경해야 함
            }
        }

        // 교환 가능한 경우의 수와 나머지 조정
        int result = max(cnt0, cnt1); 
        cout << result << '\n';
    }

    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명.

• 핵심 알고리즘:
  • 두 이진수 문자열을 비교하여 서로 다른 비트를 카운트합니다.
  • 0을 1로 바꾸는 경우(cnt0)와 1을 0으로 바꾸는 경우(cnt1)를 따로 카운트하여 최대값을 구합니다.
  • 최소 연산 횟수는 최대값(max(cnt0, cnt1))입니다.
• 구현 세부사항:
  • 문자열의 길이가 같으므로 직접 인덱스를 비교해가며 다른 비트를 카운트합니다.
  • 비트 변경은 교환 가능한 비트와 나머지 비트 조정을 고려하여 최소 연산 횟수를 구합니다.
• 시간 복잡도 분석:
  • 문자열의 길이를 n이라 할 때, 한 번의 비교는 O(n)입니다.
  • 테스트 케이스가 T개이므로 총 시간 복잡도는 O(T ⋅ n)입니다.

---

결과

제출 시, 모든 테스트 케이스에 대해 올바른 결과를 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!