[LeetCode] 926. Flip String to Monotone Increasing

 

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

Flip String to Monotone Increasing - LeetCode

Flip String to Monotone increasing

 

0과 1로만 이루어진 string 배열을 단조증가 상태로 만드는데 필요한 최소 flip 수를 구하는 문제다.

flip은 0을 1로, 1을 0으로 바꾸는 행위를 말하며

단조증가는 전체 수가 감소하지 않는 상태를 말한다.

즉, 0으로만 되어 있거나 (0000), 1로만 되어있거나 (1111) 왼쪽은 0으로만, 오른쪽은 1로만 되어 있어야 한다. (0011)

역시나 악필 풀이를 첨부한다.

 

 

핵심은 s를 앞에서부터 훑으며 그 위치의 뒤에 있는 0의 개수와, 그 위치를 포함하여 앞에 있는 1의 개수를 봐주면 된다.

해당 위치는 0과 1의 경계가 되는 지점이다.

경계는 0이 되도록 하자.

따라서 그 위치와 그 이전엔 0만, 그 위치 이후엔 1만 있게 하면 되므로,

위치 이후의 0의 개수를 세면 그게 0->1 flip 수가 되고,

위치와 위치 이전의 1의 개수를 세면 1->0 flip 수가 된다.

이를 더하면 전체 flip 수가 되고, 앞에서 부터 flip = min(flip, znum + onum) 으로 구해주면 된다.

 

00011000으로 예시를 보자.

경계는 0이 돼야 한다 취급하므로, 우리는 제일 앞에 경계가 들어갈 공간을 만들어 줘야한다.

이제 인덱스를 하나씩보면,

0일때는 가상의 공간이므로 그 뒤의 0의 개수는 6개, 그 위치와 앞에는 1이 아무것도 없다.

1일때는 0이므로, 그 뒤의 0의 개수는 앞의 0의 개수에서 하나를 뺀 5개, 그 위치와 앞에는 역시 1이 없다.

2,3일때도 0이므로 1과 같이 0의 개수를 줄인다.

4일때는 1인데, 이때는 0의 개수는 변화가 없고, 경계는 0이 돼야 한다 했으므로, 이 위치 역시 뒤집어야 한다. 그러므로 1의 개수를 증가시킨다.

5일때도 4와 같고,

6,7,8은 1과 같다.

 

즉, 해당 위치 숫자가 0일 경우엔 0의 개수를 줄이고,

1일 경우엔 1의 개수를 늘려준 후에 이를 더해주면 된다.

처음에 맨 앞의 가상 인덱스부터 훑으므로, 0의 개수는 전체 0의개수와 같고, 1의 개수는 0으로 세팅해주자.

이 때, 최소 flip 수는 전체 0의 개수이다.

 

int znum = 0, onum = 0;
for (int i=0; i<s.size(); i++) if (s[i]=='0') znum++;
int ret = znum;

그리고 s를 앞에서부터 훑으며 해당 위치 숫자가 0일 경우 znum을 감소시키고, 1일 경우 onum을 증가 시켜준다.

이 위치까지의 최소 flip 수는 min (이전 최소 flip 수, znum + onum) 이 된다.

 

for (int i=0; i<s.size(); i++) {
    if (s[i]=='0') znum--;
    else onum++;
    ret = znum + onum < ret? znum+onum:ret;
}

 

전체 코드는 아래와 같다.

 

class Solution {
public:
    int minFlipsMonoIncr(string s) {
        int znum = 0, onum = 0;
        for (int i=0; i<s.size(); i++) if (s[i]=='0') znum++;
        int ret = znum;
        for (int i=0; i<s.size(); i++) {
            if (s[i]=='0') znum--;
            else onum++;
            ret = znum + onum < ret? znum+onum:ret;
        }
        return ret;
    }
};