LeetCode - 926. Flip String to Monotone Increasing

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

 

 

문제 설명:

0과 1로 주어진 문자열이 주어진다.

0 다음 1이 나오는 순서로 만들기 위해 (0을 1로) (1을 0으로) 변환하는 최소 횟수를 리턴하라.

 

문제 풀이:

1. 0의 개수를 축적해서 기록 -> zero[]
2. 결국 000111 이런식으로 변환되는 것으로 명확한 boundary가 생기게 된다.
3. 모든 위치를 boundary로 잡고, boundary 왼쪽은 0이 되도록, 오른쪽은 1이 되도록 할 때, 바꿔야할 개수를 찾는다.
4. 결과를 저장할 변수(res)를 처음에는 '전부 1인 문자열이 되도록 할 때, flip 수'로 초기화한다.
5. 모든 boundary에서 res=min(res, 왼쪽에 1의 개수+오른쪽에 0의 개수)로 업데이트 해준다.

 

 

 

소스 코드:

class Solution {
public:
    int minFlipsMonoIncr(string S) {
        int left=0;
        int right=S.size()-1;
        int zero[20001];
        
        if(S[0]=='0') zero[0]=1;
        else zero[0]=0;
        for(int i=1;i<S.size();i++){
            if(S[i]=='1') zero[i]=zero[i-1];
            else zero[i]=zero[i-1]+1;
        }
        
        int res=zero[S.size()-1];
        for(int i=0;i<S.size();i++){
            int leftside=(i+1)-zero[i];
            int rightside=zero[S.size()-1]-zero[i];
            res=min(res,leftside+rightside);
        }
        return res;
    }
};