[Java] LeetCode 926. Flip String to Monotone Increasing

[Java] LeetCode 926. Flip String to Monotone Increasing

 

문   제 : 

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

이 문자열을 최소한의 횟수로 수정해야한다.

※ 수정하는 기준 : 

 - 증가하는 모양이여야 한다. (  ex_ 0011(O),  0010(X)  ) 

 - 0을 1로, 또는 1을 0으로 바꾸는 횟수가 최소여야 한다.

 

A binary string is monotone increasing if it consists of some number of 0's (possibly none),
followed by some number of 1's (also possibly none).

You are given a binary string s.
You can flip s[i] changing it from 0 to 1 or from 1 to 0.

Return the minimum number of flips to make s monotone increasing.

 

Example )

Input: s = "00110"
Output: 1

Explanation: We flip the last digit to get 00111.

//////////////////////////////////////////////////

Input: s = "010110"
Output: 2

Explanation: We flip to get 011111, or alternatively 000111.

---

접   근 : 

0을 1로 바꾸는 방법과 1을 0으로 바꾸는 방법 중 더 최소한의 값을 가지는 방법을 고른다.

 

---

해   결 : 

문자열 s을 돌면서 0과 1이 나온 경우로 나누어 본다.

 

0이 나왔으면

0이 나온 횟수, 1이 나온 횟수 중 최소 값을 결과값으로 저장한다.

 

1이 나왔으면

1이 나온 횟수 만큼 변수에 저장한다.

 

 

---

 

변수 선언

int flip = 0; // 1이 나온 횟수
int res = 0; // 결과

 

 

---

 

반복문을 돌면서 0이 나왔을 경우 

결과 값을 최신화 해준다.

 - 연속으로 0이 나온 횟수, 1이 나온 횟수 중 더 작은 값을 가지는 값으로!!

if(s.charAt(i) == '0') { // 0 이면 결과 최신화
    res = Math.min(res+1, flip); // 연속으로 0 나온 횟수 , 1 나온 횟수 중 최소 값
}

 

---

 

1이 나왔을 경우

변수에 카운팅해서 저장해준다.

 

else { // 1이 나온 횟수++
    flip++;
}

 

 

 

---

결   과  :

class Solution {
    public int minFlipsMonoIncr(String s) {
        int flip = 0; // 1이 나온 횟수
        int res = 0; // 결과

        for(int i=0; i<s.length(); i++){ // 모든 문자 돌면서
            if(s.charAt(i) == '0') { // 0 이면 결과 최신화
                res = Math.min(res+1, flip); // 연속으로 0 나온 횟수 , 1 나온 횟수 중 최소 값
            }

            else { // 1이 나온 횟수++
                flip++;
            }
        }

        return res;

    }
}