[LeetCode] 3666 - Minimum Operations to Equalize Binary String

문제

• 링크: https://leetcode.com/problems/minimum-operations-to-equalize-binary-string
• 난이도: Hard
• 태그: 수학, 문자열, BFS
• 결과: Time: 631 ms (13.84%), Space: 169.6 MB (23.08%)

풀이

class Solution {
public:
    int minOperations(string s, int k) {
        int n = s.size(), m = 0;
        vector<int> dist(n + 1, INT_MAX);
        vector<set<int>> nodeSets(2);
        for (int i = 0; i <= n; i++) {
            nodeSets[i % 2].insert(i);
            if (i < n && s[i] == '0') {
                m++;
            }
        }
        queue<int> q;
        q.push(m);
        dist[m] = 0;
        nodeSets[m % 2].erase(m);
        while (!q.empty()) {
            m = q.front();
            q.pop();
            int c1 = max(k - n + m, 0), c2 = min(m, k);
            int lnode = m + k - 2 * c2, rnode = m + k - 2 * c1;
            auto& nodeSet = nodeSets[lnode % 2];
            for (auto iter = nodeSet.lower_bound(lnode);
                 iter != nodeSet.end() && *iter <= rnode;) {
                int m2 = *iter;
                dist[m2] = dist[m] + 1;
                q.push(m2);
                iter = next(iter);
                nodeSet.erase(m2);
            }
        }
        return dist[0] == INT_MAX ? -1 : dist[0];
    }
};

난 손도 못댔다. 위 코드는 Editorial에서 제공되는 코드이다. 하지만 이해한 내용을 바탕으로 풀이를 써보겠다.

먼저, 문제에서 제시되는 연산은 문자의 ‘위치’와는 전혀 상관이 없다. 전체 문자열에 0이 몇 개 있는지에 집중해야한다.

문자열 $s$의 길이를 $n$, 현재 0의 개수를 $m$이라고 하자. 문제의 연산에 대해 $c$개의 0을 선택하면 1은 $k-c$개 선택된다.

이 연산을 한 번 진행한 뒤, 문자열에서 0의 개수($m’$)는 어떻게 변할까?

• 원래 있던 0중 $c$개는 뒤집혀서 1이 된다(즉, 0의 개수가 $c$만큼 감소한다).
• 원래 있던 1중 $k-c$개는 뒤집혀서 0이 된다(즉, 0의 개수가 $k-c$만큼 증가한다).

즉, $m’=m-c+(k-c)=m+k-2c$가 된다. 여기서 $c$를 1만큼 증가시키거나 감소시키는 경우를 생각해보자. 두 경우 모두 $-2$가 곱해지면서 홀짝성이 유지될 것임을 알 수 있다. 즉, 한번의 연산으로 도달할 수 있는 새로운 0의 개수 $m’$은 $m+k$와 동일한 홀짝성을 가지게 된다.

한편, $c$의 값에는 한계가 존재한다. 뒤집을 0의 개수 $c$는 현재 가지고 있는 0의 개수 $m$과 연산에서 정해진 총 뒤집기의 횟수 $k$를 초과할 수 없다. 그러므로 최댓값은 $\min(m,k)$로 정의된다.

이와 비슷하게 최솟값을 정의할 수 있다. 최대한 0을 뽑지 않으려고 해도 1의 개수가 부족하다면 어쩔 수 없이 0을 뒤집어야하는 상황이 생길 수 있다. 1의 개수는 $n-m$개이므로, 나머지 $k-(n-m)$개 만큼은 0을 뒤집어야한다. 그러므로 최솟값은 $\max(0,k-(n-m))$으로 정의된다.

이상을 종합하면, $\min(m,k)\leq c\leq\max(0,k-(n-m))$이다. $m’=m+k-2c$이므로 $c$의 최솟값과 최댓값으로부터 $m’$의 최솟값과 최댓값을 구할 수 있다.

• $m’$의 최솟값 $L$: $c$가 가장 클 때 빼는 값이 커지므로 이 때가 $m’$의 최솟값이다.
  • $L=m+k-2\cdot\min(m,k)$
• $m’$의 최댓값 $R$: $c$가 가장 작을 때 빼는 값이 작아지므로 이 때가 $m’$의 최댓값이다.
  • $R=m+k-2\cdot\max(0,k-(n-m))$

따라서, 한 번의 연산으로 갈 수 있는 다음 상태는 $[L,R]$ 범위 안에 있으면서 $m+k$와 홀짝성이 같은 모든 숫자가 된다.

0의 개수를 하나의 노드로 정의하고, $m$에서 한 번의 연산으로 갈 수 있는 $m’$을 간선으로 연결하면 이 문제를 그래프로 모델링할 수 있다. 문제에서 요구하는 것은 모든 문자를 1로 만들기 위한 최소 연산 횟수이므로 곧 최단 경로를 찾는 문제가 된다. 간선의 길이는 모두 1로 동일하므로 BFS를 활용하는 것이 적합하다.

아직 방문하지 않은 숫자는 set으로 관리한다. $m’$값들은 $c$ 값을 어떻게 선택하든 항상 2씩 차이나므로 한 번의 연산으로 도달할 수 있는 상태들은 모두 같은 홀짝성을 갖는다. 이 사실을 이용하여 set를 홀수와 짝수로 나누면 더 효율적으로 탐색할 수 있다. 추가로, BFS를 통해 방문한 숫자는 여기서 하나씩 지워나가며, lower_bound를 활용해 시간복잡도를 낮춘다(전체를 뒤지지 않고 이진탐색으로 찾아내므로).

위의 풀이 내용을 종합하여 주석을 추가한 코드는 아래와 같다.

class Solution {
public:
    int minOperations(string s, int k) {
        int n = s.size(), m = 0;
        vector<int> dist(n + 1, INT_MAX);
        
        // nodeSets[0]: 짝수 상태
        // nodeSets[1]: 홀수 상태
        vector<set<int>> nodeSets(2);
        for (int i = 0; i <= n; i++) {
            nodeSets[i % 2].insert(i);
            if (i < n && s[i] == '0') { // 초기 문자열에서 0의 개수를 셈
                m++;
            }
        }
        queue<int> q;
        q.push(m);
        dist[m] = 0;
        nodeSets[m % 2].erase(m); // 출발점은 방문했으므로 제거
        while (!q.empty()) {
            m = q.front();
            q.pop(); // 현재 0의 개수
            
            // 뒤집을 0의 개수의 최솟값, 최댓값 계산
            int c1 = max(k - n + m, 0), c2 = min(m, k);
            
            // 연산 후 가능한 새로운 0의 개수 범위를 도출
            // m' = m + k - 2c 공식을 사용함
            int lnode = m + k - 2 * c2, rnode = m + k - 2 * c1;
            
            // m + k의 홀짝성에 따라 nodeSet 선택
            auto& nodeSet = nodeSets[lnode % 2];
            
            // lower_bound로 범위 내의 방문하지 않은 숫자를 빠르게 탐색
            for (auto iter = nodeSet.lower_bound(lnode);
                 iter != nodeSet.end() && *iter <= rnode;) {
                int m2 = *iter; // 새로 도달한 '0의 개수' 상태
                dist[m2] = dist[m] + 1;
                q.push(m2);
                iter = next(iter);
                nodeSet.erase(m2);
            }
        }
        
        // 목적지인 0개 상태에 도달했다면 그 거리를 반환하고, 그렇지 않으면 -1을 반환
        return dist[0] == INT_MAX ? -1 : dist[0];
    }
};

배운 점과 후기

Daily Question이었는데, 너무 어려웠다. Hint를 다 봐도 이해가 안돼서 Editorial까지 자세히 읽었다. Discussion 창을 보면 나만 어려웠던 것은 아니었는지 모두가 통곡(…)을 하고 있었다

게다가 뭔가 DP로 풀릴 것 같기도 하고, 뭔가 ‘발상의 전환으로 쉽게 해결할 수 있을 것 같아보이지?’라는 냄새를 풍기는 문제라 더 오래 고민했다. 결국 Editorial보고 그것마저도 이해못해서 AI의 도움을 받았지만.

좌절스러운 난이도의 문제였다. 그래도 난이도가 Hard인데다 다들 어려움을 토로하는 문제였으니 위안이 된다.