0과 1을 포함하는 이진 문자열 input_str이 주어졌다고 가정합니다. 우리의 임무는 주어진 문자열에서 1을 교환하여 0과 1을 그룹화하는 것입니다. 최소한의 스왑 작업을 수행해야 하며 해당 값을 반환해야 합니다. 한 가지 명심해야 할 점은 인접한 값만 바꿀 수 있다는 것입니다.
따라서 입력이 input_str =10110101과 같으면 출력은 4
가 됩니다.스왑은 다음과 같습니다 -
10110101->01110101->01111001->01111010->01111100
총 스왑 수:4.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- one :=1이 있는 input_str의 위치를 포함하는 새 목록
- mid :=(1/2 크기)의 하한선
- res :=0
- 0에서 1까지의 범위에 있는 i에 대해 다음을 수행합니다.
- res :=res + |one[mid] - one[i]| - |중간 - 나는|
- res <0이면
- 0을 반환
- 그렇지 않으면
- 반환 결과
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(input_string):
one = [i for i in range(len(input_string)) if input_string[i] == "1"]
mid = len(one) // 2
res = 0
for i in range(len(one)):
res += abs(one[mid] - one[i]) - abs(mid - i)
return 0 if res < 0 else res
print(solve('10110101')) 입력
'10110101'
출력
4