Problem From.
https://leetcode.com/problems/flip-string-to-monotone-increasing/
오늘 문제는 binary string 이 주어졌을 때, 그것을 monotone increasing 하게 바꾸는데 필요한 최소 flip 수를 반환하는 문제였다.
처음에는 monotone increasing 하게 바꾸는게 뭔지 몰랐는데, 단순하게 생각하면 1 이후에는 0이 나오지 않게 바꾸는 것이었다.
이 문제는 DP 를 이용하여 푸는 문제였다.
제일 처음에 문자가 없는 경우 dp[0] = 0 이 된다.
또한 문제가 하나만 있는 경우도 뒤집지 않아도 되기 때문에 0이 된다.
문제는 그 다음부터인데, 다음에 붙는 수가 1이라면 앞의 수가 0 이던 1 이던 관계없이 monotone increasing 하기 때문에 0이 된다.
하지만 다음에 붙는 수가 0 이라면 두가지 경우로 나뉘게 된다.
0 을 그대로 붙이는 경우 앞에 나온 1을 모두 0으로 바꿔야 한다.
0 을 1 로 바꾸고 붙이는 경우 한번의 flip 을 거치게 된다.
위의 과정을 계속 반복하기 위해서 지금까지 나온 1 의 수와 0을 1 로 바꾸는 과정을 계속 누적해 나가는게 핵심이었다.
class Solution {
fun minFlipsMonoIncr(s: String): Int {
var addOne = 0
var considerFlip = 0
for (i in 0 until s.length) {
if (s[i] == '1') {
addOne += 1
} else {
considerFlip += 1
}
considerFlip = Math.min(addOne, considerFlip)
}
return considerFlip
}
}위의 풀이를 보면 addOne 은 지금까지 더한 1의 갯수가 누적되어 있고, considerFlip 은 0을 1 로 바꾸는 수가 누적되어 있다.
Math.min 을 사용하여 그 상황에 앞의 1을 모두 0으로 바꾸는게 더 좋은지, 아니면 붙는 0을 1로 바꾸는게 더 좋은지 판별하게 하였다.
위 문제의 시간복잡도는 O(n) 이 된다.
