Python에서 이진 문자열을 교체하는 데 필요한 최소 변경 사항을 찾는 프로그램

<시간/>

이진 문자열 s가 있다고 가정합니다. 1비트를 뒤집을 수 있는 연산을 고려해 보겠습니다. 두 개의 인접한 문자가 동일하지 않으면 문자열 s를 교대 문자열이라고 합니다. 우리는 s를 교대로 만드는 데 필요한 최소 작업 수를 찾아야 합니다.

따라서 입력이 s ="11100011"과 같으면 출력은 3이 됩니다. 왜냐하면 위치 1, 4, 7에서 비트를 뒤집으면 "10101010"이 되고 모두 교대로 되기 때문입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

변경 :=0
짝수_1 :=0, 짝수_0 :=0
홀수_1 :=0, 홀수_0 :=0
범위 0에서 s - 1까지의 i에 대해 수행
- 내가 짝수이면
  - s[i]가 '1'과 같으면
    - 짝수_1 :=짝수_1 + 1
  - 그렇지 않으면
    - 짝수_0 :=짝수_0 + 1
- 그렇지 않으면
  - s[i]가 '1'과 같으면
    - 홀수_1 :=홀수_1 + 1
  - 그렇지 않으면
    - 홀수_0 :=홀수_0 + 1
(even_1+odd_0)> (even_0+odd_1)이면
- 변경 :=even_0 + odd_1
그렇지 않으면
- 변경 :=even_1 + odd_0
반환 변경

예제(파이썬)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. &minnus;

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"