Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 이진 문자열을 교대 패턴으로 만드는 최소 스왑 횟수 구하기

문제 개요

길이가 짝수이고 0과 1의 개수가 같은 이진 문자열이 주어졌을 때, 이 문자열을 교대(alternating) 형태로 만들기 위해 필요한 최소 스왑 횟수를 구하는 것이 이번 문제의 목표입니다. 여기서 교대 문자열이란 0101... 또는 1010...처럼 인접한 두 문자가 서로 같지 않은 문자열을 의미합니다.

예시

예를 들어 입력 문자열이 "11110000"라면, 앞쪽의 1들과 뒤쪽의 0들을 적절히 맞바꿔 "10101010" 또는 "01010101" 형태로 만들어야 하며, 이때 필요한 스왑 횟수는 2회입니다.

알고리즘 접근 방법

이 문제의 핵심은 스왑이 항상 1 하나와 0 하나를 맞바꾸는 연산이라는 점입니다. 이미 올바른 자리에 놓인 문자는 그대로 두고, 잘못된 자리에 있는 문자들끼리만 서로 교환하면 되므로, 위치 그룹별로 문자 개수만 세면 최소 스왑 횟수를 바로 계산할 수 있습니다.

  1. 문자열의 짝수 인덱스(0, 2, 4, ...)와 홀수 인덱스(1, 3, 5, ...)에 있는 0의 개수를 각각 세어 evenZeroCnt, oddZeroCnt에 저장합니다.
  2. 같은 방식으로 짝수 인덱스와 홀수 인덱스에 있는 1의 개수를 세어 evenOneCnt, oddOneCnt에 저장합니다.
  3. 0으로 시작하는 패턴(0101...)을 만드는 경우: 짝수 인덱스에는 0이, 홀수 인덱스에는 1이 위치해야 하므로, 짝수 인덱스에 있는 1들을 홀수 인덱스의 0들과 맞바꾸면 됩니다. 필요한 스왑 횟수는 min(evenOneCnt, oddZeroCnt)입니다.
  4. 1로 시작하는 패턴(1010...)을 만드는 경우: 반대로 홀수 인덱스의 1들을 짝수 인덱스의 0들과 맞바꾸면 되므로, 필요한 스왑 횟수는 min(oddOneCnt, evenZeroCnt)입니다.
  5. 최종 답은 위 두 경우 중 더 작은 값, 즉 min(zeroStartSwaps, oneStartSwaps)입니다.

두 후보 값 중 작은 값을 선택하면, 주어진 문자열에서 가장 적은 교환으로 도달할 수 있는 교대 패턴을 자동으로 찾게 됩니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;

int getMinSwaps(string str) {
    int oddZeroCnt = 0;
    int evenZeroCnt = 0;
    int oddOneCnt = 0;
    int evenOneCnt = 0;
    int n = str.length();

    // 짝수/홀수 인덱스별로 0과 1의 개수를 센다
    for (int i = 0; i < n; ++i) {
        if (i % 2 == 0) {
            if (str[i] == '1') {
                ++evenOneCnt;
            } else {
                ++evenZeroCnt;
            }
        } else {
            if (str[i] == '1') {
                ++oddOneCnt;
            } else {
                ++oddZeroCnt;
            }
        }
    }

    // 0으로 시작하는 패턴(0101...)으로 만들 때 필요한 스왑 횟수
    int zeroStartSwaps = min(evenOneCnt, oddZeroCnt);

    // 1로 시작하는 패턴(1010...)으로 만들 때 필요한 스왑 횟수
    int oneStartSwaps = min(oddOneCnt, evenZeroCnt);

    return min(zeroStartSwaps, oneStartSwaps);
}

int main() {
    string str = "11110000";
    cout << "Minimum swaps = " << getMinSwaps(str) << endl;
    return 0;
}

위 프로그램을 컴파일하여 실행하면 다음과 같은 결과가 출력됩니다.

실행 결과

Minimum swaps = 2

복잡도 분석

문자열을 한 번만 순회하면 되므로 시간 복잡도는 O(n)이며, 추가적인 배열 없이 몇 개의 카운터 변수만 사용하므로 공간 복잡도는 O(1)입니다.