<Hard> Create Maximum Number (LeetCode : C#)

https://leetcode.com/problems/create-maximum-number/

📕 문제 설명

길이가 각각 m, n인 두 정수 배열 nums1과 nums2과 k가 주어진다. nums1과 nums2는 두 수의 자릿수를 나타낸다. nums1과 nums2를 조합해서 k개의 자릿수만큼 숫자를 만들 때 가장 큰 숫자 만들기

동일한 array의 자릿수의 상대적 순서는 보존된다.

• Input
  nums1, nums2, k
• Output
  nums1과 nums2를 k개의 자릿수만큼 조합해서 가장 큰 수 만들기

예제

풀이

public class Solution {
    public int[] MaxNumber(int[] nums1, int[] nums2, int k) {
        int m = nums1.Length;
        int n = nums2.Length;
        int[] result = new int[k];
        for (int i = Math.Max(0, k - n); i <= k && i <= m; i++)
        {
            // 최대 하위배열 nums1과 nums2에서 가져오기 (모든 케이스)
            int[] candidate = MergeArrays(GetMaxSubsequence(nums1, i), GetMaxSubsequence(nums2, k - i));
            if (IsGreater(candidate, 0, result, 0)) result = candidate; // 새로 만든게 더 크면 갱신하기 
        }
        return result;
    }

    private int[] GetMaxSubsequence(int[] nums, int k)
    {
        int[] result = new int[k];
        int length = 0;
        
        for (int i = 0; i < nums.Length; i++) // 큰 하위 배열 찾는 과정
        {
            while (length > 0 && nums[i] > result[length - 1] && nums.Length - i + length > k) length--;
            if (length < k) result[length++] = nums[i];
        }
        return result;
    }

    private int[] MergeArrays(int[] nums1, int[] nums2)
    {
        int m = nums1.Length;
        int n = nums2.Length;
        int[] merged = new int[m + n];
        int i = 0, j = 0, idx = 0;
    
        while (i < m && j < n)
        {
            if (IsGreater(nums1, i, nums2, j)) merged[idx++] = nums1[i++]; // nums1 더 크니까 병합정렬 값에 nums1 넣어주기 -> 다음 인덱스로 증가
            else merged[idx++] = nums2[j++];  // nums2가 더크니까 그 다음 병합 정렬 값에 nums2 넣어주기 -> 다음 인덱스로 증가
        }   
        while (i < m) merged[idx++] = nums1[i++]; // 남은 nums1 채워넣기
        while (j < n) merged[idx++] = nums2[j++]; // 남은 nums2 채워넣기
        
        return merged; // 정렬된 병합 배열 반환 
    }

    private bool IsGreater(int[] nums1, int idx1, int[] nums2, int idx2)
    {
        int m = nums1.Length;
        int n = nums2.Length;
        
        while (idx1 < m && idx2 < n)
        {
            if (nums1[idx1] > nums2[idx2]) return true;
            else if (nums1[idx1] < nums2[idx2]) return false;
            
            idx1++;
            idx2++;
        }
        
        return idx1 != m;
    }
}

결과