[LeetCode][926] Flip String to Monotone Increasing

문제 : https://leetcode.com/problems/flip-string-to-monotone-increasing/description/

---

문자열을 앞에서부터 탐색하면서 1과 0의 개수를 센다.

00110이 있다면 1로 바꿔야 하는 0은 1보다 뒤에 위치한다. (00110)

1은 앞에 나오는것부터 바꿔야 하므로 처음부터 세어준다.

지금 세어주는 수가 현재부터 0 혹은 1을 반대 수로 flip 할 때 바꿔야 하는 최소 횟수가 된다.

만약 0을 바꾸는 것 보다 1을 바꾸는게 더 이득이라면 1을 바꾸는횟수로 초기화한다.

예를들어, 1010011이 있다면 4번째 인덱스까지 탐색했을 때 0의 개수(3)는 1의 개수(2)보다 크다.

따라서 앞에서 나오는 1들을 모두 0으로 바꾸면 된다. -> 0000011

반대의 경우는 불가능하다.

왜냐하면 앞에는 0이 나와야하므로 앞을 0으로 바꾸는 것은 항상 자유롭다.

하지만 앞을 1로 바꾼다면 앞으로 나올 뒤의 모든 숫자들도 1로 바꿔야하기 때문이다.

이런 식으로 모든 문자열을 탐색할때까지 0, 1을 바꾸는 횟수를 세어주었을 때 두 수 중 최소값이 정답이된다.

그리디 알고리즘이라고 보면 될 것 같다. 

시간복잡도는 O(N).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/926.%20Flip%20String%20to%20Monotone%20Increasing.cpp