문제 설명
이진 문자열(binary string) s가 주어졌다고 가정해 보겠습니다. 문자열의 일부 접두사(prefix)를 잘라 맨 뒤로 이동(회전)할 수 있을 때, 인접한 두 문자가 서로 같지 않도록 — 즉 0과 1이 번갈아 나타나는 교대(alternating) 패턴을 만들기 위해 뒤집어야 하는 문자의 최소 개수를 구하는 것이 목표입니다.
예를 들어 입력이 s = "10010101111"이라면 정답은 2입니다. 접두사 "10"을 잘라 뒤로 붙이면 문자열은 "01010111110"이 되고, 여기서 오른쪽에서 세 번째와 다섯 번째 비트를 0으로 뒤집으면 "01010101010"이 완성되기 때문입니다.
알고리즘 접근 방식
핵심 아이디어는 문자열을 두 배로 확장해 모든 회전(rotation) 경우를 단일 슬라이딩 윈도우로 검사하는 것입니다. 길이가 N인 문자열의 모든 회전 결과는 길이 2N인 확장 문자열 위에서 길이 N짜리 윈도우를 이동시키면 한 번의 순회로 모두 확인할 수 있습니다. 해결 절차는 다음과 같습니다.
ans와 N에 S의 길이를 저장하고, 누적 변수 s는 0으로 초기화합니다.
i를 0부터 2*N - 1까지 반복하며 s에 int(S[i mod N]) XOR (i AND 1) 값을 더합니다. 이는 각 위치에서 기준 교대 패턴("0,1,0,1,...")과 얼마나 어긋나는지를 세는 과정입니다.
i >= N - 1이 되는 순간부터 윈도우가 유효해지므로, ans를 ans, s, N - s 중 최솟값으로 갱신합니다. 여기서 s는 "0101..." 패턴 기준 불일치 수, N - s는 "1010..." 패턴 기준 불일치 수입니다.
윈도우에서 벗어난 가장 왼쪽 문자의 기여분을 s에서 빼 줍니다.
모든 반복이 끝나면 ans를 반환합니다.
구현 예제
다음 파이썬 구현을 통해 더 쉽게 이해할 수 있습니다.
class Solution:
def solve(self, S):
ans = N = len(S)
s = 0
for i in range(2 * N):
s += int(S[i % N]) ^ (i & 1)
if i >= N - 1:
ans = min(ans, s, N - s)
s -= int(S[(i - (N - 1)) % N]) ^ ((i - (N - 1)) & 1)
return ans
ob = Solution()
s = "10010101111"
print(ob.solve(s))
입력
"10010101111"
출력
2
복잡도 분석
확장된 문자열을 한 번만 순회하므로 시간 복잡도는 O(N)입니다. 추가 배열 없이 몇 개의 변수만 사용하므로 공간 복잡도는 O(1)입니다. 덕분에 문자열 길이가 매우 큰 경우에도 효율적으로 동작합니다.