23.01.17 Today’s Leetcode
926. Flip String to Monotone Increasing
1
이 시작되는 index를 찾는것이 이 문제의 핵심이다. 가장 최소의 flip number을 구해야 하기 때문에,
이 index를 찾는게 생각보다 까다로운데 차근차근히 생각해보면 쉽다. index 기준으로 왼쪽에 있는 1
의 갯수와 오른쪽에 있는 0
의 갯수가 가장 작을 때가
minimum flip을 위한 최적의 index이다. 왼쪽에 있는 1
을 모두 뒤집어야 하고, 오른쪽에 있는 0
을 모두 뒤집어야 하기 때문이다.
class Solution:
def minFlipsMonoIncr(self, s: str) -> int:
n = len(s)
if n == 1:
return 0
one_counter = [0] * n
zero_counter = [0] * n
# zero_counter[i] means that # of '1' between s[:i]
# one_counter[i] means that # of '1' between s[i:]
one_counter[0] = (1 if s[0] == '1' else 0)
zero_counter[n - 1] = (1 if s[n - 1] == '0' else 0)
for i in range(1, n):
one_counter[i] = one_counter[i - 1] + (1 if s[i] == '1' else 0)
for i in range(n - 2, -1, -1):
zero_counter[i] = zero_counter[i + 1] + (1 if s[i] == '0' else 0)
res = 10**9
for i in range(n):
res = min(res, one_counter[i] + zero_counter[i] - 1)
return res