1. 문제

Given two integer arrays arr1 and arr2, return the minimum number of operations (possibly zero) needed to make arr1 strictly increasing.

In one operation, you can choose two indices 0 <= i < arr1.length and 0 <= j < arr2.length and do the assignment arr1[i] = arr2[j].

If there is no way to make arr1 strictly increasing, return -1.

두 개의 정수 배열 arr1과 arr2가 주어질 때, arr1이 엄격한 오름차순 정렬이 되기 위해 필요한 최소 연산 수를 return 하라.
한 연산 당 arr1[i] = arr2[j] (0 <= i < arr1.length, 0 <= j < arr2.length)

2-1. Top-down Dynamic Programming

class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        dp = {}
    	arr2.sort()

      def dfs(prev, i):
          # i가 range를 벗어날 경우 0을 return
          if i >= len(arr1):
              return 0
          # dp 배열 안에 dfs(prev, i) 값이 이미 존재하면 return (메모이제이션)
          if (prev, i) in dp:
              return dp[(prev, i)]

          cost = float('inf')

          # 이미 arr1[i]가 prev보다 크면, arr[i + 1:]의 최소 횟수를 구해 cost에 넣는다
          # 아닐 경우 cost는 inf로 유지
          # 현재 값이 prev보다 작은 경우에는 값을 안 바꾸면 답이 없다는 뜻이다
          if arr1[i] > prev:
              cost = dfs(arr1[i], i + 1)

          # 현재 index의 값을 교체할 경우 값 구하기 (이진탐색)
          idx = bisect.bisect_right(arr2, prev)

          # arr2에 존재?
          if idx < len(arr2):
              # 존재할 경우, 현재 값 바꾸지 않을 경우 (cost)와 바꿀 경우 (1 + dfs(arr2[idx], i + 1)) 중,
              # 더 작은 값을 cost에 할당한다
              cost = min(cost, 1 + dfs(arr2[idx], i + 1))

          dp[(prev, i)] = cost
          return cost

    dfs(-1, 0)
    return dp[(-1, 0)] if dp[(-1, 0)] < float('inf') else -1

1. arr2를 정렬한다.
2. 해시 맵 dp를 초기화한다.
3. arr[i - 1] = prev일 때 arr[i:]를 정렬할 수 있는 최소 연산 수를 계산하는 함수 dfs(i, prev)를 정의합니다.
   • (i, prev)가 dp 안에 존재하는지 확인하고, 있다면 dp[(i, prev)]를 return
   • cost를 float('inf')로 초기화
   • arr1[i] > prev라면, cost를 dfs(i + 1, arr1[i])로 세팅
   • 이진 검색을 사용하여 arr2에서 prev보다 큰 가장 작은 값의 idx를 찾음, idx < len(arr2)라면, cost를 min(cost, 1 + dfs(i + 1, arr2[idx]))로 세팅
   • dp[(i, prev)]를 cost로 업데이트
   • cost를 return

dfs(i, prev): arr[i - 1] = prev일 때 arr[i:]를 정렬된 배열로 만들 수 있는 최소 연산 수를 계산

2-2. Bottom-up Dynamic Programming

class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        dp = {-1: 0}
        arr2.sort()
        n = len(arr2)
        
        # 매 반복마다, arr1[:i+1]까지의 최소 연산 수를 계산
        for i in range(len(arr1)):
            new_dp = collections.defaultdict(lambda: float('inf'))
            # dp 딕셔너리에 저장된 이전 인덱스까지의 경우의 수를 사용
            for prev in dp:
            	# arr1[i]가 prev보다 크면(이미 증가), new_dp[arr[i]]를 new_dp[arr1[i]]와 dp[prev] 둘 중 작은 것으로 할당한다(전 단계까지 중 가장 최솟값을 선택한다)
                if arr1[i] > prev:
                    new_dp[arr1[i]] = min(new_dp[arr1[i]], dp[prev])
                    
                # 이진 탐색을 사용해 arr2에서 arr1의 현재 인덱스에 할당할 값의 위치 찾기
                idx = bisect.bisect_right(arr2, prev)
                
                # arr2에 존재하면?
                if idx < n:
                	# 바꿨을 경우에 대한 값 할당
                    new_dp[arr2[idx]] = min(new_dp[arr2[idx]], 1 + dp[prev])
            dp = new_dp

        return min(dp.values()) if dp else -1

1. arr2를 정렬한다
2. 해시 맵 dp를 {-1: 0}으로 초기화한다.
3. new_dp를 arr1의 각 인덱스 개수만큼 float('inf')로 초기화한다
4. dp의 각 키를 반복한다
   • arr1[i]가 prev보다 크면: new_dp[arr1[i]]를 min(new_dp[arr1[i], dp[arr1[i]) 로 업데이트합니다.
   • 그렇지 않으면: arr2에서 이전 값보다 큰 가장 작은 값의 인덱스 idx를 찾아, 값이 존재하면 new_dp[arr2[idx]]를 min(new_dp[arr2[idx], 1 + dp[prev])로 업데이트합니다.

3. 복잡도 계산

3-1. Top-down의 경우

arr1, arr2의 길이를 각각 m, n이라고 할 때, 시간복잡도: O(m ⋅ n ⋅ logn)

• arr2를 정렬 -> O(n ⋅logn)
• 알고리즘의 효율을 높이기 위해 메모이제이션을 사용, 해시 맵 dp에 (i, prev)일 경우의 미니멈을 저장함. m개의 인덱스 / arr[i]를 arr2의 값으로 대체하기 위한 최대 prev의 경우의 수 n + 1
• arr2에 대한 binary search로 계산되므로 O(logn)이 소모

공간복잡도: O(m ⋅ n) --> dp의 최대 크기

3-2. Bottom-up의 경우

arr1, arr2의 길이를 각각 m, n이라고 할 때, 시간복잡도: O(m ⋅ n ⋅ logn)

• arr2를 정렬 -> O(n ⋅logn)
• dp를 m 라운드씩 업데이트, 인덱스 i의 각 라운드에서 arr1[i]의 n개 값 중 하나로 바꾸거나 변경하지 않고 그대로 둘 수 있으므로 가능한 딕셔너리 키는 최대 n+1개
• arr2에 대한 binary search로 계산되므로 O(logn)이 소모

공간복잡도: O(n)