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

https://leetcode.com/problems/minimum-swaps-to-group-all-1s-together-ii/description/?envType=daily-question&envId=2024-08-02

leetcode - Minimum Swaps to Group All 1's Together II

문제 유형 : 슬라이딩 윈도우

문제 난이도 : Medium

 

문제

A swap is defined as taking two distinct positions in an array and swapping the values in them.

A circular array is defined as an array where we consider the first element and the last element to be adjacent.

Given a binary circular array nums, return the minimum number of swaps required to group all 1's present in the array together at any location.

 

swap은 두 개의 다른 위치의 값을 변경하는 것을 말한다.

이진의 원형 배열이 주어진다. 첫 번째와 마지막 요소도 인접한 것으로 간주한다.

모든 1들이 붙어있도록 하기 위한 최소 swap 횟수를 구하시오.

 

풀이

https://leetcode.com/problems/minimum-swaps-to-group-all-1s-together-ii/solutions/5571822/sliding-window-45ms-beats-99-61/?envType=daily-question&envId=2024-08-02

의 도움을 받았다.

슬라이딩 윈도우와 0의 개수를 이용해서 답을 구하는 것까지는 스스로 생각했었는데, 스스로 힘으로 풀어낼 수는 없었다. 스스로 실망스럽고, 자책하게 된다.

 

모든 1이 붙어있으려면, 결국 길이가 1의 개수만큼의 1만으로 이루어진 부분배열공간이 있어야 한다.

그리고, 그 공간에 있는 0의 개수가 곧 swap해야하는 개수이고, 즉, 원형 배열 속 길이가 count of 1인 부분배열에서 가장 적은 0의 개수를 구해야 한다.

 

즉, 길이가 1의 개수인 창을 움직이면서, 그 속의 0의 개수를 세주면 된다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int minSwaps(vector<int>& nums) {
        int n = nums.size();
        int n1 = count(nums.begin(), nums.end(), 1);
        if(n1 == 0 || n1 == n) return 0;

        int ans = INT_MAX;
        int countOfOnes = 0;
        for(int i = 0; i < n1; i++) {
            if(nums[i]) countOfOnes++;
        }

        for(int i = n1; i < n + n1; i++) {
            countOfOnes -= nums[(i - n1 + n) % n];
            countOfOnes += nums[i % n];

            ans = min(ans, n1 - countOfOnes);
        }
        return ans;
    }
};