2134 Minimum Swaps to Group All 1's Together II

 

Account Login - LeetCode

 

Weekly Contest 275에 위치한 4점짜리 문제이다.

이 문제는 Medium 난이도답게 어렵게 생각할 필요 없이 직관적으로 두 단계를 거치면 해결할 수 있는 문제이다.

1. 배열에서 '1'의 개수 세기

2. 배열을 순회하며 각 지점에서 1이 연속적으로 위치하려면 얼마나 swap이 필요한지 세기

 

2번 단계의 경우 단순한 브루트 포스 방식으로 해결하면 시간이 오래 걸릴 수도 있지만 의외로 슬라이딩 윈도우 방식을 사용하면 간단하게 해결할 수 있다.

먼저 배열의 처음부터 1이 연속적으로 위치하려면 몇 번의 swap이 필요한지 세아린다. 이때의 횟수를 저장하고

이후부터는 슬라이딩 윈도우를 한 칸 이동시키며 슬라이딩 윈도우에 새롭게 추가되고 없어진 부분만을 고려하며 진행하면 된다.

 

class Solution {
public:
    int minSwaps(vector<int>& nums) {
        int n = 0;
        int size = nums.size();
        
        for(int i = 0; i < size; ++i) {
            n += nums[i];
        }
        
        int curr = 0;
        for(int i = 0; i < n; ++i) {
            curr += nums[i];
        }
        
        int minimum = n - curr;
        for(int i = 1; i < size; ++i) {
            curr -= nums[i - 1];
            curr += nums[(i + n - 1) % size];
            minimum = min(minimum, n - curr);
        }

        return minimum;
    }
};