C++로 배열을 엄격하게 증가하는 배열로 만들기: 최소 교체 연산 구하기

문제 이해하기

정수를 저장하는 두 개의 배열 arr1과 arr2가 있다고 가정해 봅시다. 우리의 목표는 arr1을 엄격하게 증가(strictly increasing)하는 배열, 즉 모든 원소가 바로 앞 원소보다 큰 배열로 만드는 데 필요한 최소 연산 횟수를 구하는 것입니다.

여기서 허용되는 연산은 하나뿐입니다. 두 개의 인덱스 0 <= i < n과 0 <= j < m을 선택한 뒤, arr1[i] = arr2[j]와 같이 값을 대입하는 것입니다. 여기서 n과 m은 각각 arr1과 arr2의 크기를 의미합니다.

만약 어떻게 해도 arr1을 엄격하게 증가하는 배열로 만들 수 없다면 -1을 반환해야 합니다.

예시

입력이 arr1 = [1,5,3,7,8], arr2 = [1,3,2,5]라고 해 보겠습니다. 이때 출력은 1입니다. arr1의 값 5를 arr2의 값 2로 딱 한 번 교체하면 배열이 [1,2,3,7,8]이 되어 엄격하게 증가하기 때문입니다.

풀이 접근 방식

이 문제는 동적 계획법(DP)과 이분 탐색(upper_bound)을 조합하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 배열의 각 위치에서 "현재 원소를 그대로 둘 것인가", 아니면 "arr2의 값으로 교체할 것인가"라는 두 가지 선택지를 고려하면서, 최소 교체 횟수를 메모이제이션으로 저장하는 것입니다.

solve() 함수의 동작 단계

solve() 함수는 배열 arr1, 배열 arr2, 인덱스 i, j, 직전 값 prev, 그리고 2차원 배열 dp를 매개변수로 받습니다.
i >= arr1.size()라면 배열의 끝에 도달한 것이므로 1을 반환합니다.
j를 upper_bound를 이용해 prev보다 큰 arr2의 첫 번째 원소 위치로 갱신합니다.
dp[i][j] != -1이라면 이미 계산된 값이므로 그대로 반환합니다(메모이제이션).
ret := arr2.size() + 1로 초기화합니다. 이는 "교체 불가능" 상태를 나타내는 초기값입니다.
prev < arr1[i]라면 현재 원소를 그대로 두는 경우를 고려하여 ret = min(ret, solve(arr1, arr2, i + 1, j, arr1[i], dp))로 갱신합니다.
j < arr2.size()라면 현재 원소를 arr2[j]로 교체하는 경우를 고려하여 ret = min(ret, 1 + solve(arr1, arr2, i + 1, j, arr2[j], dp))로 갱신합니다.
최종적으로 dp[i][j] = ret을 저장한 뒤 반환합니다.

메인 함수에서 수행하는 작업

배열 arr2를 오름차순으로 정렬합니다.
n := arr1.size(), m := arr2.size()로 설정합니다.
크기가 2005 × 2005인 2차원 배열 dp를 선언하고 모든 값을 -1로 채웁니다.
ret := solve(arr1, arr2, 0, 0, -INF, dp)를 호출합니다.
ret > arr2.size()라면 -1을, 그렇지 않다면 ret - 1을 반환합니다.

아래 구현 예시를 통해 더 자세히 이해해 보겠습니다.

구현 예제 (C++)

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(vector<int>& arr1, vector<int>& arr2, int i, int j, int prev, vector<vector<int> >& dp){
      if (i >= arr1.size())
         return 1;
      j = upper_bound(arr2.begin() + j, arr2.end(), prev) - arr2.begin();
      if (dp[i][j] != -1)
         return dp[i][j];
      int ret = arr2.size() + 1;
      if (prev < arr1[i]) {
         ret = min(ret, solve(arr1, arr2, i + 1, j, arr1[i], dp));
      }
      if (j < arr2.size()) {
         ret = min(ret, 1 + solve(arr1, arr2, i + 1, j, arr2[j], dp));
      }
      return dp[i][j] = ret;
   }
   int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2){
      sort(arr2.begin(), arr2.end());
      int n = arr1.size();
      int m = arr2.size();
      vector<vector<int> > dp(2005, vector<int>(2005, -1));
      int ret = solve(arr1, arr2, 0, 0, INT_MIN, dp);
      return ret > arr2.size() ? -1 : ret - 1;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,5,3,7,8}, v1 = {1,3,2,5};
   cout << (ob.makeArrayIncreasing(v,v1));
}

실행 결과

입력

{1,5,3,7,8}, {1,3,2,5}

출력

복잡도 분석

상태의 개수는 최대 n × m개이며, 각 상태에서 upper_bound 이분 탐색에 O(log m)이 소요되므로 전체 시간 복잡도는 O(n · m · log m)입니다. 공간 복잡도는 메모이제이션 테이블을 위해 O(n · m)입니다. 이 접근법을 사용하면 완전 탐색으로는 기하급수적으로 늘어나는 경우의 수를 효율적으로 줄일 수 있습니다.