926. Flip String to Monotone Increasing (문자열을 뒤집어서 모노톤 증가시키기)

이진 문자열은 몇 개의 숫자  0(없을 수도 있음)과 몇 개의 숫자 1(없을 수도 있음)로 구성된 경우 증가하는 모노톤입니다.

이진 문자열  s가 주어집니다. s[i]를 0을 1로 또는 1을 0으로 뒤집을 수 있습니다.

증가하는 모노톤 s를 만드는데 최소 뒤집기 횟수를 반환합니다.

예시 1:

입력: s = "00110"
출력: 1
설명: 마지막 숫자를 뒤집어 00111을 얻습니다.

예시 2:

입력: s = "010110"
출력: 2
설명: 뒤집어서 011111, 또는 000111을 얻습니다.

예시 3:

입력: s = "00011000"
출력: 2
설명: 뒤집어서 00000000을 얻습니다.

 

조건:

• 1 <= s.length <= 10⁵
• s[i]는 '0' 또는 '1'중 하나입니다.

정답:

public class Solution {
    public int MinFlipsMonoIncr(string s) {
        int oneCount = 0;
        int flipCount = 0;
        foreach (var c in s)
        {
            if (c == '1') 
            {
                oneCount += 1;
            } 
            else if (oneCount > 0) 
            {
                flipCount += 1;
            }
            flipCount = Math.Min(oneCount, flipCount);
        }

        return flipCount;
    }
}

해설: 

문자열을 탐색하며 1이 나올땐 oneCount을 증가시켜주고 0이 나올땐 oneCount가 0보다 클때 증가시켜주었습니다.

"1000"을 예시로 왼쪽 기준으로 1의 갯수를 셀때 1에서 flipCount는 0이고 oneCount는 1이기 때문에 0입니다.

그 이후 0에서 oneCount가 0보다 크기 때문에 flipCount도 1이되고 oneCount는 더 이상 올라가지 않기 때문에 flipCount는 2에서 더 올라가지 않게 되고 oneCount와 lipCount중 더 작은 값인 1만 반환하게 됩니다.