[LeetCode] 1888 - Minimum Number of Flips to Make the Binary String Alternating

문제

• 링크: https://leetcode.com/problems/minimum-number-of-flips-to-make-the-binary-string-alternating
• 난이도: Medium
• 태그: 문자열, 다이나믹 프로그래밍
• 결과: Time: 291 ms (5.26%), Space: 118.8 MB (5.26%)

Editorial 풀이

class Solution {
public:
    int minFlips(string s) {
        auto I = [](char ch, int x) -> int { return ch - '0' == x; };

        int n = s.size();
        vector<vector<int>> pre(n, vector<int>(2));
        for (int i = 0; i < n; ++i) {
            pre[i][0] = (i == 0 ? 0 : pre[i - 1][1]) + I(s[i], 1);
            pre[i][1] = (i == 0 ? 0 : pre[i - 1][0]) + I(s[i], 0);
        }

        int ans = min(pre[n - 1][0], pre[n - 1][1]);
        if (n % 2 == 1) {
            vector<vector<int>> suf(n, vector<int>(2));
            for (int i = n - 1; i >= 0; --i) {
                suf[i][0] = (i == n - 1 ? 0 : suf[i + 1][1]) + I(s[i], 1);
                suf[i][1] = (i == n - 1 ? 0 : suf[i + 1][0]) + I(s[i], 0);
            }
            for (int i = 0; i + 1 < n; ++i) {
                ans = min(ans, pre[i][0] + suf[i + 1][0]);
                ans = min(ans, pre[i][1] + suf[i + 1][1]);
            }
        }

        return ans;
    }
};

pre 배열

• pre[i][j]: s[0..i]를 j로 끝나는 교대 문자열로 만들기 위한 최소 flip 횟수
• pre[i][0]: i번째가 0으로 끝나려면 → 이전은 1로 끝나야하고, s[i]가 1이면 flip 필요
• pre[i][1]: i번째가 1로 끝나려면 → 이전은 0으로 끝나야하고, s[i]가 0이면 flip 필요

  n이 짝수인 경우

  n이 짝수면 비트 회전을 적용해도 0101… ↔ 1010… 사이에서만 바뀌므로 전체를 한 번에 변환하는 경우만 고려하면 된다.

  n이 홀수인 경우

  비트 회전을 적용했을 때 교대문자열이 아니게 될 수 있다. n이 홀수일 때 교대 문자열은 시작과 끝이 같은 값이다. (예: 10101, 01010)

비트회전(Type1 연산)을 통해 앞부분을 뒤로 보내는 것은 아래와 같이 생각할 수 있다.

[ s[0..i] | s[i+1..n-1] ]
          ↓
[ s[i+1..n-1] | s[0..i] ]

이 결과가 0으로 시작해서 0으로 끝나는 패턴이 되려면?

• suf[i][j]: s[i..n-1]를 j로 시작하는 교대 문자열로 만들기 위한 최소 flip 횟수
• s[i+1..n-1]은 0으로 시작해야 함 → suf[i+1][0]
• s[0..i]은 0으로 끝나야 함 → pre[i][0] 반대로 1로 시작해서 1로 끝나는 패턴이 되려면?
• s[i+1..n-1]은 1로 시작해야 함 → suf[i+1][1]
• s[0..i]은 1로 끝나야 함 → pre[i][1]

그래서 모든 분할점을 시도해서 최솟값을 구한다.