이진 문자열(binary string)이 주어졌을 때, 문자열 내 임의의 위치에 모든 1을 연속적으로 그룹화하기 위해 필요한 최소 스왑(교환) 횟수를 구하는 문제입니다.
예를 들어 입력이 "10101001101"이라면, 출력은 3이 됩니다. 이는 "00000111111"처럼 모든 1을 하나로 묶는 것이 가능하기 때문입니다.
문제 해결 접근 방식
이 문제는 슬라이딩 윈도우(Sliding Window)와 누적 합(Prefix Sum) 기법을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 문자열에 있는 1의 총 개수를 셉니다. 이 값이 곧 윈도우의 크기가 됩니다.
- 길이가 '1의 개수'와 같은 윈도우를 문자열 위에서 왼쪽부터 오른쪽으로 이동시키면서, 각 윈도우 안에 포함된 1의 개수를 누적 합 배열로 빠르게 계산합니다.
- 윈도우 안에 없는 1의 개수(즉, 스왑이 필요한 1의 개수)의 최솟값이 곧 정답입니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- data := 주어진 문자열을 비트 리스트로 변환
- one := 0, n := 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, data):
data = list(map(int, list(data)))
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()
print(ob.solve("10101001101"))입력
"10101001101"
출력
3
복잡도 분석
누적 합 배열을 한 번 생성하는 데 O(n)의 시간이 걸리고, 윈도우를 이동시키는 과정 역시 O(n)이므로 전체 시간 복잡도는 O(n)입니다. 추가로 사용되는 공간은 누적 합 배열 때문에 O(n)입니다. 덕분에 문자열 길이가 매우 긴 경우에도 효율적으로 최소 스왑 횟수를 계산할 수 있습니다.