801. Minimum Swaps To Make Sequences Increasing

[zeikar]

Problem link

https://leetcode.com/problems/minimum-swaps-to-make-sequences-increasing/

Problem Summary

nums1, nums2 배열의 같은 위치의 원소를 swap 해서 배열을 증가하게 만드는 (strictly increasing) 최소 swap 횟수를 구하는 문제.

Solution

현재 인덱스에서 swap 한다 / 안한다 두 가지를 할 수 있고 이를 dp로 풀 수 있다.

swap 처리가 약간 까다롭긴 한데 swapped 변수에 따라 이전 인덱스 비교를 다르게 해서 풀 수 있다.

Source Code

class Solution:
    def minSwap(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        
        @cache
        def swap(idx, swapped):
            if idx == n:
                return 0
            
            ret = 987654321
            if swapped:
                if nums1[idx - 1] < nums2[idx] and nums2[idx - 1] < nums1[idx]:
                    ret = min(ret, swap(idx + 1, False))

                if nums1[idx - 1] < nums1[idx] and nums2[idx - 1] < nums2[idx]:
                    ret = min(ret, swap(idx + 1, True) + 1)
                    
            else:
                if nums1[idx - 1] < nums1[idx] and nums2[idx - 1] < nums2[idx]:
                    ret = min(ret, swap(idx + 1, False))

                if nums1[idx - 1] < nums2[idx] and nums2[idx - 1] < nums1[idx]:
                    ret = min(ret, swap(idx + 1, True) + 1)

            return ret

        return min(swap(1, False), swap(1, True) + 1)