2134. Minimum Swaps to Group All 1's Together II

문제

링크

Input:

nums = [0,1,0,1,1,0,0]

nums = [0,1,1,1,0,0,1,1,0]

nums = [1,1,0,0,1]

Output:

1 ([0, 1, 0, 1, 1, 0, 0] -> [0, 0, 1, 1, 1, 0, 0])

2 ([0, 1, 1, 1, 0, 0, 1, 1, 0] -> [1, 1, 1, 0, 0, 0, 0, 1, 1])

0

서식:

class Solution {
public:
    int minSwaps(vector<int>& nums) {
        
    }
};

요약:

0과 1로만으로 이루어진 이진배열이 주어진다

주어진 이진배열 안에 값이 1인 요소들을 최소한의 swap을 통해 일렬로 나열해야 한다

이때 최소한의 swap 횟수를 구하라

 

주의!

이 이진 배열은 원형으로 이루어져 있다

좀 더 풀어서 이야기하자면 첫 번째 요소와 마지막 요소는 서로 인접해 있기에 [1, 0, 0, 0, 1]의 경우 값이 1인 요소들이 일렬로 나열되어 있다고 볼 수 있다

조건:

1 <= nums.length <= $10^5$
nums [i]는 0 or 1이다

---

풀이 과정

이해:

이 문제에서는 단순히 생각을 해보면 아주 쉽다

최소한의 움직임을 구해야 하는데 이러한 상황에서는 적어도 아니, 아무리 못해도 1개의 1은 위치가 고정된다는 것이다.

모든 1들을 swap 하게 되면 그것은 애초에 답이 될 수 없는 상황이기에 최소한 한 개의 1은 위치가 고정된다는 가정하에, 그 1을 나열된 1들 중 가장 첫 번째 1이라고 생각을 하면 된다

 

조금 풀어서 이야기하자면 우리는 최소한의  swap으로 1이 연속된 작은 배열을 만드는 것이다

그리고 최소한 한 개의 1은 움직이지 않을 것이며 이를 토대로 우리는 고정된 1을 작은 배열의 처음이라고 생각하고 거기서부터 총 1의 개수만큼의 인덱스들을 모두 참조해 0의 개수를 구하게 되면 이는 1이 0으로 swap이 되어야 하기에 0의 개수 == swap 횟수가 되는 것이다

 

문제 나누기:

여기서 우리가 구해야 하는 것은 2가지다

1. 총 1의 개수
2. 작은 배열 안의 0의 개수

위 두 가지를 가지고 nums를 순회하며 각 인덱스마다 인덱스 + 총 1의 개수만큼의 작은 배열 안에 있는 0을 구하며 이들 중 가장 적은 0의 개수를 출력하면 될 것이다

결론:

하지만 이대로 문제를 풀게 된다면 nums의 길이 $n$, 총 1의 개수 $k$라고 하였을 때,$O(n * k)$가 되는데 이는 잠재적인 최대 $O(n^2)$ 이 될 수 있기에 피해야 한다

 

그렇기에 우리는 획기적인 알고리즘이 필요하다

풀이:

획기적인 알고리즘으로는 sliding window가 있다 window(범위)를 정하고 sliding을 하는 것

이 문제에서는 window(총 1의 개수)를 정하고 nums에서  0의 개수를 가지고 sliding(이동)을 하면서 0의 개수를 매번 갱신시키는 것

1. 미리 nums의 첫 번째 부분에서의 작은 배열에서의 0의 개수를 구한다
2. 인덱스를 움직이면서 작은 배열에서 빠져나가는 요소와 새로 추가되는 요소가 0이라면 적절한 조치를 취한다
   • 빠져나가는 요소가 0인 경우: 0의 개수 - 1
   • 새로 추가되는 요소가 0인 경우: 0의 개수 + 1
3. nums 끝까지 순회하면서 nums [i]의 요소가 1일 때마다 0의 개수를 비교하여 더 적은 수를 따로 저장

시간복잡도:

nums의 길이 $n$

nums의 첫 번째 인덱스의 작은 배열 내에서 0의 개수 구하기 $k$

$$O(n + k)$$

코드 및 설명:

class Solution {
public:
    int minSwaps(vector<int>& nums) {
        int totalOne = 0;

        // get number of one
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] == 1)
                totalOne++;
        }

        if (totalOne < 2)
            return 0;

        // set window end
        // and count zero
        int end = totalOne - 1;
        int zeroNum = getZero(nums, 0, totalOne);

        // find lowest number of zero;
        int ans = zeroNum;
        for (int i = 1; i < nums.size(); ++ i) {
            if (end + i == nums.size())
                end -= nums.size();

            if (nums[i - 1] == 0)
                zeroNum--;
            if (nums[end + i] == 0)
                zeroNum++;
            if (nums[i] == 1)
                ans = min(ans, zeroNum);
        }

        return ans;
    }
};

 

---

 

P.S.

일단 머릿속에서 떠오르는 방식을 그대로 채용한 것인데 이게 sliding window라는 것을 처음 알았다

그리고 사실 sliding window 기법을 사용한 것은 아닌것 같다

다른 사람들이 쓴 코드들을 보니 슬라이딩 윈도우를 굉장히 효율적이고 잘 활용한 것 같은 케이스들이 많았는데 아무래도 생전 처음 적용해 봤으니 그렇게 효율적이지 못하게 코드를 짠 것 같다

그래도 새로운 알고리즘을 배웠으니 유익한 시간이었다

---