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

[zeikar]

Problem link

https://leetcode.com/problems/minimum-swaps-to-group-all-1s-together-ii/

Problem Summary

1을 임의의 0과 swap해서 1이 연속되게 만드는 문제. 단, 배열은 원형이다

Solution

한 덩어리로 만든다고 생각해보면 1이 나온 개수만큼 어딘가에 뭉쳐놓는다고 볼 수 있다. 그렇게 되면 슬라이딩 윈도우 방법으로 1이 나온 개수 크기의 윈도우로 배열을 순회하면서 그 윈도우 안의 0의 개수가 swap 횟수가 된다.

원형 처리는 간단하게 배열을 그냥 뒤에 그대로 붙여서 해결하였다. 어차피 O(n)으로 큰 차이 없다.

Source Code

class Solution:
    def minSwaps(self, nums: List[int]) -> int:
        n = len(nums)
        ones = nums.count(1)
        zeros = nums[:ones].count(0)

        nums = nums + nums

        ans = 987654321
        for i in range(ones, 2*n):
            ans = min(ans, zeros)

            if nums[i] == 0:
                zeros += 1
            if nums[i - ones] == 0:
                zeros -= 1

        return ans