문제 설명
이진 문자열 s가 주어졌다고 가정해 봅시다. 수행할 수 있는 연산은 비트 하나를 선택해 그 값을 뒤집는 것(0을 1로, 또는 1을 0으로)입니다. 목표는 세 개의 동일한 비트가 연속으로 등장하지 않는 문자열을 만드는 것이며, 이때 필요한 최소 연산 횟수를 구해야 합니다.
예를 들어 입력이 s = "10011100"이라면 출력은 1입니다. 인덱스 4의 비트 1을 0으로 뒤집어 "10010100"을 만들면 더 이상 세 개의 연속된 동일 비트가 존재하지 않기 때문입니다.
접근 방법
이 문제를 해결하는 핵심 아이디어는 같은 비트가 연속으로 이어지는 구간(run)을 찾아내는 것입니다. 길이가 n인 연속 구간을 모두 길이 2 이하의 조각으로 분할하려면 최소 n // 3번의 뒤집기가 필요합니다. 비트 하나를 뒤집으면 해당 구간이 두 조각으로 나뉘는데, 각 조각의 길이가 2를 넘지 않도록 배치할 수 있기 때문입니다.
따라서 다음 단계로 진행합니다.
- l := 0, count := 0으로 초기화합니다.
- l이 문자열 길이보다 작은 동안 다음을 반복합니다.
- r := l로 설정합니다.
- r이 문자열 길이보다 작고 s[r]이 s[l]과 같은 동안 r을 1씩 증가시켜 현재 연속 구간의 끝을 찾습니다.
- count에 (r - l) // 3을 더합니다. 여기서 (r - l)은 현재 연속 구간의 길이입니다.
- l := r로 갱신하여 다음 구간부터 탐색을 이어갑니다.
- count를 반환합니다.
예제 코드
아래 파이썬 구현을 통해 더 자세히 이해해 보겠습니다.
def solve(s):
l = 0
count = 0
while l < len(s):
r = l
while r < len(s) and s[r] == s[l]:
r += 1
count += (r - l) // 3
l = r
return count
s = "10011100"
print(solve(s))입력
"10011100"
출력
1
복잡도 분석
이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 메모리를 거의 사용하지 않아 공간 복잡도는 O(1)입니다. 따라서 매우 긴 이진 문자열에 대해서도 효율적으로 동작합니다.