문제 개요
이진 문자열 s가 주어졌다고 가정해 봅시다. 한 번의 연산으로 특정 위치의 비트 하나를 뒤집을 수 있으며, 인접한 두 문자가 서로 같지 않은 문자열을 교대 문자열(alternating string)이라고 합니다. 우리가 구해야 할 것은 문자열 s를 교대 문자열로 만들기 위해 필요한 최소 연산 횟수입니다.
예를 들어 입력이 s = "11100011"이라면 출력은 3이 됩니다. 인덱스 1, 4, 7의 비트를 뒤집으면 "10101010"이 되어 모든 문자가 교대 형태를 이루기 때문입니다.
접근 방법
교대 문자열은 다음 두 가지 패턴 중 하나만 가능합니다.
- '1'로 시작하는 패턴: "10101010..." — 짝수 인덱스에는 '1', 홀수 인덱스에는 '0'이 위치
- '0'으로 시작하는 패턴: "01010101..." — 짝수 인덱스에는 '0', 홀수 인덱스에는 '1'이 위치
따라서 각 패턴과 일치하지 않는 문자의 개수를 센 뒤, 더 작은 값을 선택하면 됩니다. 해결 절차는 다음과 같습니다.
- change := 0으로 초기화
- even_1 := 0, even_0 := 0 (짝수 인덱스에서 '1'과 '0'의 개수)
- odd_1 := 0, odd_0 := 0 (홀수 인덱스에서 '1'과 '0'의 개수)
- i를 0부터 s의 길이 - 1까지 반복:
- i가 짝수이면:
- s[i]가 '1'이면 even_1을 1 증가
- 그렇지 않으면 even_0을 1 증가
- i가 홀수이면:
- s[i]가 '1'이면 odd_1을 1 증가
- 그렇지 않으면 odd_0을 1 증가
- i가 짝수이면:
- (even_1 + odd_0) > (even_0 + odd_1)이면 change := even_0 + odd_1 ('1'로 시작하는 패턴에 필요한 변경 횟수)
- 그렇지 않으면 change := even_1 + odd_0 ('0'으로 시작하는 패턴에 필요한 변경 횟수)
- change 반환
여기서 even_0 + odd_1은 "1010..." 패턴을 만들기 위해 뒤집어야 하는 비트 수이고, even_1 + odd_0은 "0101..." 패턴을 만들기 위해 뒤집어야 하는 비트 수입니다. 두 값 중 작은 것이 곧 최소 변경 횟수가 됩니다.
Python 코드 예제
아래 구현을 통해 더 잘 이해할 수 있습니다.
def solve(s):
change = 0
even_1 = 0
even_0 = 0
odd_1 = 0
odd_0 = 0
for i in range(len(s)):
if(i % 2 == 0):
if(s[i] == '1'):
even_1 += 1
else:
even_0 += 1
else:
if(s[i] == '1'):
odd_1 += 1
else:
odd_0 += 1
if((even_1 + odd_0) > (even_0 + odd_1)):
change = even_0 + odd_1
else:
change = even_1 + odd_0
return change
s = "11100011"
print(solve(s))입력
"11100011"
출력
3
복잡도 분석
이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 고정된 개수의 카운터 변수만 사용하므로 공간 복잡도는 O(1)입니다. 여기서 n은 문자열의 길이입니다.