[2024] day 216. Leetcode 2134. Minimum Swaps to Group All 1's Together II

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 8월 2일 (금)
Leetcode daily problem

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

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

Problem

swap은 배열에서 서로 다른 두 위치를 취하고 그 위치의 값을 바꾸는 것으로 정의한다.
원형 배열(circular) 은 첫 번째 요소와 마지막 요소가 인접하다고 간주하는 배열로 정의한다.

이진 원형 배열(binary circular array)인 nums가 주어지면 배열에 있는 모든 1을 임의의 위치에 함께 그룹화하는 데 필요한 최소 스왑 수를 반환한다.

Solution

sliding window

주어진 원형 배열에서 1을 연속된 그룹으로 만들기 위해 필요한 스왑 수를 찾기 위해 슬라이딩 윈도우를 사용해서 해결해볼 수 있다.
배열이 원형이므로 배열을 두 번 반복한다고 생각한 다음,
배열에서 모든 1의 개수를 센다. 1의 개수 만큼 연속된 자리를 만들어야 하므로, 배열을 확장한다음 길이가 1의 개수 만큼인 윈도우를 슬라이딩하면서 1의 개수를 샌다. 최대 개수의 1이 포함된 윈도우를 찾고, 이 윈도우 안에 포함된 0의 개수를 세서 최소 스왑 수를 계산한다.

Code

class Solution:
    def minSwaps(self, nums: List[int]) -> int:
        n = len(nums)
        total_ones = sum(nums)
        
        if total_ones == 0:
            return 0
        
        extended_arr = nums + nums
        
        cur_ones = sum(extended_arr[:total_ones])
        max_ones = cur_ones
        
        for i in range(1, n):
            cur_ones += extended_arr[i+total_ones-1] - extended_arr[i-1]
            max_ones = max(cur_ones, max_ones)
            
        return total_ones - max_ones

Complexicity

시간 복잡도

주어진 배열의 모든 원소를 순회하면서 1의 개수를 세기 때문에 O(n)이 소요된다. 그리고 확장된 배열을 만들면서 두 번 이어 붙이는 과정에서 O(n)의 시간복잡도가 되며 배열의 크기는 2n이 된다.

아래에서 슬라이딩 윈도우 로직에서 첫 번째 윈도우 1의 개수를 계싼하는데 O(n) 나머지 윈도우를 슬라이딩하면서 1의 개수를 업데이트 하는데 O(n)이 소요되어 총 시간복잡도는 O(n) 이다.

공간 복잡도

배열을 확장하면서 추가적인 공간이 필요하므로 O(n)의 공간복잡도가 소요된다. 나머지는 상수 공간을 차지하므로 전체 공간복잡도는 O(n) 이다.