3666. Minimum Operations to Equalize Binary String

 

https://leetcode.com/problems/minimum-operations-to-equalize-binary-string/description/?envType=daily-question&envId=2026-03-03

Minimum Operations to Equalize Binary String - LeetCode

 

이 문제는 0 과 1  로 이루어진 문자열이 주어지고 k 라는 정수가 주어질 때, 문자열의 k 개를 선택하여 뒤집기를 여러번 반복해서 문자열의 모든 문자가 1로 이루어지기 위한 최소 연산 횟수를 구하는 문제입니다.

 

핵심 아이디어

이 문제는 0 과 1의 위치는 신경쓰지 않습니다. 

그래서 k 개 flip 의 결과를 0 의 개수 혹은 1의 개수로 표현하는 것이 가능합니다.

현재 상태에서 flip 된 결과들이 다음 상태! 

 

예를 들어서

111000 이라는 문자열이 존재하고 k 가 3일 때, 0의 개수는 3이고, 가능한 다음 상태는 다음과 같습니다.

000000 001100 110100 111111 라는 4개의 상태가 존재합니다.

 

0 의 개수를 노드

flip 을 현재 노드에 연결된 노드들의 간선이라고 해석하면

 

이 문제는 현재 노드에서 0의 개수가 0개인 노드와의 최단 거리를 구하는 문제라고 정의할 수 있습니다.

 

현재 노드에 대한 거리는 배열로 설정하고, 0 노드와의 최단 거리는 BFS 를 이용하여 구할 수 있습니다.

 

import java.util.*;

class Solution {
    public int minOperations(String s, int K) {
        int n = s.length();
        int z0 = 0;
        for (char c : s.toCharArray()) if (c == '0') z0++;

        if (z0 == 0) return 0;
        if (K > n) return -1;

        // parity 불가능 판정
        if ((K % 2 == 0) && (z0 % 2 == 1)) return -1;

        // dist[z] = 최소 연산
        int[] dist = new int[n + 1];
        Arrays.fill(dist, -1);

        ArrayDeque<Integer> q = new ArrayDeque<>();
        dist[z0] = 0;
        q.add(z0);

        while (!q.isEmpty()) {
            int z = q.poll();
            int d = dist[z];
            if (z == 0) return d;

            int ones = n - z;

			// 이 코드 영역 중요
            // 선택 가능한 a 범위: a는 "0에서 고르는 개수"
            int L = Math.max(0, K - ones); // a >= K - (n - z)
            int U = Math.min(K, z);        // a <= z

            if (L > U) continue;

            // 이 z에서 갈 수 있는 모든 z' 생성
            for (int a = L; a <= U; a++) {
                int z2 = z + K - 2 * a; // z' = z + K - 2a
                // z2는 자동으로 0..n 범위 안에 들어감(위 범위가 보장)
                if (dist[z2] == -1) {
                    dist[z2] = d + 1;
                    q.add(z2);
                }
            }
        }

        return -1;
    }
}

 

 

 

            // 선택 가능한 a 범위: a는 "0에서 고르는 개수"
            int L = Math.max(0, K - ones); // a >= K - (n - z)
            int U = Math.min(K, z);        // a <= z

 

a 의 의미는 0 에서 고르는 수를 의미합니다.

예를들어서 0이 3개라면 a=1 일 때, 0 = 2 , 1 = 4 가 됩니다.

 

원래 a 는 0 <= a <= k 가 되지만 현재 0 과 1의 개수에 의해서 이 범위보다 더 좁아질 수 있습니다.

 

a 의 최대 범위는 a <= z 입니다. 왜냐하면 a 의 의미가 0 에서 고르는 개수를 의미하므로

a 의 최소 범위는 a >= k - (n - z) 입니다. 왜냐하면 n - z = a 의 개수. 0 에서 a 개를 고르면, 1에서는 k - a 개를 선택해야 합니다.

그러므로 a 는 k-a 보다는 크거나 같아야 합니다. 0 이하면 0으로.

 

 

그리고 이 코드 부분도 중요합니다. 

int z2 = z + K - 2 * a; // z' = z + K - 2a

 

다음 0 의 개수 z2 = z - a + k - a 입니다.

z 에서 0을 선택한다는 것은 현재 z 에서 a 만큼 뺀다는 것이고, 그만큼 k-a 가 1에서 선택되고 이건 0 이되므로 k - a 만큼 더합니다.

 

 

하지만 이 알고리즘은 한번 더 최적화가 필요합니다.

 

이 알고리즘의 최악의 상황을 가정해봅시다.

 

n = 100000

k = 50000 

 

이라고 할 때,

 

L ... U 차이는 50000 입니다.

이 차이의 의미는 BFS 가 다음 노드를 탐색할 때 루프가 50000 번 돈다는 것입니다.

 

            // 이 z에서 갈 수 있는 모든 z' 생성
            for (int a = L; a <= U; a++) {
                int z2 = z + K - 2 * a; // z' = z + K - 2a
                // z2는 자동으로 0..n 범위 안에 들어감(위 범위가 보장)
                if (dist[z2] == -1) {
                    dist[z2] = d + 1;
                    q.add(z2);
                }
            }

 

 

dist[z2] == -1 로 q 에 쌓이는 노드는 그렇게 많아보이지 않더라도, 지금 로직상에서는 노드 개수와 상관없이 탐색되는 범위가 줄어들지 않아 각 노드에서 L ... U 까지의 범위를 계속 탐색하게 됩니다.

하지만 이 범위의 노드들은 이미 상당 부분 이미 방문될 가능성이 높습니다.

 

그래서 이 범위를 방문되지 않은 노드들로 한정지을 방법을 찾아야 할 것 같습니다.

 

BFS 는 사실 저 큰 틀에서는 최적화 할 부분이 없는거 같고, 현재 노드에서 다음 노드로 가는 로직을 최적화 해야하는 게 자연스러운 사고 흐름인 것 같습니다.

 

현재 범위에서 탐색되지 않는 노드 찾기

특정 범위 내에 숫자들을 뽑아서 가져오는 방법은 Java 에서는 TreeSet 이 있습니다.

미방문 노드를 TreeSet 에 넣고, 여기서 특정 범위 내에 존재하는 노드들을 가져와서 없애는 방식으로 방문 처리를 할 수 있습니다.

 

더 최적화 하는 방법 

z` = z  + K - 2a 이고 이게 현재 노드에서 다음 노드로 가는 공식.

z + K 의 결과에 따라서 z` 는 짝수/홀수로 고정됩니다.

7 이라고 하면 여기서 -2 씩 줄어드므로 z` 는 홀수

6 이라고 하면 여기서 -2 씩 줄어드므로 z` 는 짝수가 됩니다.

 

그러므로 ( z + K ) % MOD 2 = z` 가 됩니다.

이 특성 때문에 TreeSet 을 짝수 / 홀수 로 나눠서 사용합니다.

 

 

import java.util.*;

class Solution {
    public int minOperations(String s, int K) {
        int n = s.length();
        int z0 = 0;
        for (char c : s.toCharArray())
            if (c == '0')
                z0++;

        if (z0 == 0)
            return 0;
        if (K > n)
            return -1;

        // parity 불가능 판정
        if ((K % 2 == 0) && (z0 % 2 == 1))
            return -1;

        // dist[z] = 최소 연산
        int[] dist = new int[n + 1];
        Arrays.fill(dist, -1);

        TreeSet<Integer> evenSet = new TreeSet<>();
        TreeSet<Integer> oddSet = new TreeSet<>();

        for (int i = 0; i <= n; i++)
            if (i % 2 == 0)
                evenSet.add(i);
            else
                oddSet.add(i);

        ArrayDeque<Integer> q = new ArrayDeque<>();
        dist[z0] = 0;
        q.add(z0);

        while (!q.isEmpty()) {
            int z = q.poll();
            int d = dist[z];
            if (z == 0)
                return d;

            int ones = n - z;
            // 선택 가능한 a 범위: a는 "0에서 고르는 개수"
            int L = Math.max(0, K - ones); // a >= K - (n - z)
            int U = Math.min(K, z);        // a <= z


            if (L > U)
                continue;

            //다음 최소,최대 0 의 개수.
            int minZ = z + K - 2 * U;
            int maxZ = z + K - 2 * L;

            int parity = (z + K) % 2;

            TreeSet<Integer> set = (parity == 0) ? evenSet : oddSet;

            NavigableSet<Integer> subset = set.subSet(minZ, true, maxZ, true);

            Iterator<Integer> it = subset.iterator();

            while (it.hasNext()) {
                int z2 = it.next();
                it.remove();

                dist[z2] = d + 1;
                q.add(z2);
            } 

        }

        return -1;
    }
}