[LeetCode/Kotlin]Medium - 926. Flip String to Monotone Increasing

Flip String to Monotone Increasing - LeetCode

 

---

Problem

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 1:

Input: s = "00110"
Output: 1
Explanation: We flip the last digit to get 00111.

Example 2:

Input: s = "010110"
Output: 2
Explanation: We flip to get 011111, or alternatively 000111.

Example 3:

Input: s = "00011000"
Output: 2
Explanation: We flip to get 00000000.

Constraints:

• 1 <= s.length <= 105
• s[i] is either '0' or '1'.

 

---

Solution

나의 풀이법

풀이 접근 과정

모든 index를 기준으로 값을 변경하는 모든 경우의 수를 계산하는 방법을 선택하였습니다.

예를 들어 현재 index 값이 3이면, 모든 1의 값을 0으로 바꾸거나, 모든 0의 값을 1로 바꾸거나, 3 앞은 0으로, 뒤는 1로 바꾸는 방법입니다.

최종 소스코드

class Solution {
    fun minFlipsMonoIncr(s: String): Int {
        var answer = Int.MAX_VALUE
        var zeroCount = 0
        var oneCount = 0
        var beforeZeroCount = 0
        var beforeOneCount = 0

        s.forEach { if (it == '0') zeroCount += 1 else oneCount += 1 }
        s.forEachIndexed { idx, i ->
            if (i == '0') beforeZeroCount += 1 else beforeOneCount += 1
            answer = minOf(answer, zeroCount, oneCount, beforeOneCount+zeroCount-beforeZeroCount)
        }

        return answer
    }
}

1. 입력받은 문자열에서 0의 개수와 1의 개수를 각각 zeroCount와 oneCount에 계산합니다.
2. s를 기준으로 forEach를 돕니다.
   1. 현재 값이 0이면 현재 index 기준으로 beforeZeroCount 개수를 +1 합니다.
   2. 현재 값이 1이면 현재 index 기준으로 beforeOneCount 개수를 +1 합니다.
   3. 각 경우의 수의 최솟값을 구하고 answer에 계산합니다.
      1. answer
      2. 모든 0을 1로 바꾸는 개수(zeroCount)
      3. 모든 1을 0으로 바꾸는 개수(oneCount)
      4. 현재 index를 기준으로 앞은 0으로, 뒤는 1로 바꾸는 개수 (beforeOneCount+zeroCount-beforeZeroCount)
3. answer를 리턴합니다.

 

---

Comment

이건 접근 방법이 까다로웠습니다.

좀 더 깔끔하고 간결한 방법이 있을 수 있지만, 복잡하게 생각하지 않고 그냥 단순히 모든 index를 기준으로 계산하는 방법을 선택했습니다.

그래도 O(N)으로 완료…