Python으로 이진 문자열의 모든 1을 한곳에 모으는 최소 스왑 횟수 계산하기

문제 개요

이진 문자열이 주어졌을 때, 임의의 두 비트를 서로 교환(swap)할 수 있다고 가정해 봅시다. 이때 문자열 안의 모든 1을 연속된 하나의 그룹으로 모으기 위해 필요한 최소 스왑 횟수를 구하는 것이 목표입니다.

예를 들어 입력이 s = "0111001"이라면, 출력은 1이 됩니다. 다음과 같은 스왑 한 번만 수행하면 되기 때문입니다.

0111001 -> 1111000

접근 방법: 슬라이딩 윈도우와 누적 합

이 문제는 슬라이딩 윈도우(Sliding Window) 기법과 누적 합(Prefix Sum) 배열을 활용하면 효율적으로 해결할 수 있습니다.

핵심 아이디어는 다음과 같습니다.

전체 문자열에서 1의 개수를 세어 one이라고 합니다.
길이가 one인 윈도우를 문자열 위에서 왼쪽부터 오른쪽으로 한 칸씩 이동시키며 검사합니다.
각 윈도우 내부에 포함된 1의 개수를 누적 합 배열로 빠르게 구합니다.
윈도우 안에 있어야 할 1의 개수(one)에서 실제로 윈도우 안에 있는 1의 개수를 빼면, 그 윈도우를 채우기 위해 필요한 스왑 횟수가 됩니다.
모든 윈도우 위치 중 최솟값이 곧 정답입니다.

알고리즘 단계

주어진 이진 문자열을 0과 1의 정수 리스트 data로 변환합니다.
one := 0, n := len(data)로 초기화합니다.
크기가 n인 누적 합 배열 summ을 만들고 0으로 채운 뒤, summ[0] := data[0]으로 설정합니다.
one := one + data[0]
i가 1부터 n-1까지 반복합니다.
- summ[i] := summ[i - 1] + data[i]
- one := one + data[i]
ans := one으로 초기화합니다.
left := 0, right := one - 1로 설정합니다.
right < n인 동안 반복합니다.
- left가 0이면 temp := summ[right], 그렇지 않으면 temp := summ[right] - summ[left - 1]
- ans := min(ans, one - temp)
- right와 left를 각각 1씩 증가시킵니다.
ans를 반환합니다.

Python 구현 예제

아래 코드를 통해 실제 동작을 확인해 보겠습니다.

class Solution(object):
    def solve(self, s):
        data = list(map(int, list(s)))
        one = 0
        n = len(data)
        summ = [0 for i in range(n)]
        summ[0] = data[0]
        one += data[0]
        for i in range(1, n):
            summ[i] += summ[i-1] + data[i]
            one += data[i]
        ans = one
        left = 0
        right = one - 1
        while right < n:
            if left == 0:
                temp = summ[right]
            else:
                temp = summ[right] - summ[left-1]
            ans = min(ans, one - temp)
            right += 1
            left += 1
        return ans

ob = Solution()
s = "0111001"
print(ob.solve(s))

입력

"0111001"

출력

복잡도 분석

누적 합 배열을 만드는 데 O(n), 윈도우를 이동시키며 검사하는 데 O(n)이 걸리므로, 전체 시간 복잡도는 O(n)입니다. 공간 복잡도 역시 누적 합 배열 때문에 O(n)입니다. 덕분에 문자열 길이가 길어져도 선형 시간 안에 최소 스왑 횟수를 구할 수 있습니다.