Python에서 모든 1을 함께 그룹화하는 데 필요한 스왑 수를 계산하는 프로그램

<시간/>

이진 문자열이 있고 두 비트를 교환할 수 있다고 가정합니다. 모든 1을 함께 그룹화하는 데 필요한 최소 스왑 수를 찾아야 합니다.

따라서 입력이 s ="0111001"과 같으면 다음 스왑을 수행할 수 있으므로 출력은 1이 됩니다. 0111001 -> 1111000.

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

data :=주어진 이진 문자열의 0과 1 목록
1:=0, n:=데이터 배열 길이로 설정
크기가 n인 배열 합계를 만들고 이를 0으로 채우고 summ[0] :=data[0]으로 설정
하나 :=하나 + 데이터[0]
1 ~ n – 1 범위의 i에 대해
- sum[i] :=summ[i - 1] + 데이터[i]
- 하나 :=하나 + 데이터[i]
an :=하나
왼쪽 :=0, 오른쪽 :=1 – 1
오른쪽
left가 0이면 temp :=summ[right], 그렇지 않으면 temp :=summ[right] – summ[left - 1]
ans :=ans의 최소값, 1 – temp
오른쪽과 왼쪽을 1씩 증가

반환

예제(파이썬)

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

class Solution(object):
   def solve(self, s):
      data = list(map(int, list(s)))
      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()
s = "0111001"
print(ob.solve(s))

입력

"0111001"