[LeetCode] 321. Create Maximum Number

😎풀이

1. nums1에서 몇 개의 숫자를 뽑을지 정하는 i를 통해 순회한다. 최솟값은 0이며, 최댓값은 nums1을 모두 뽑거나, k개를 뽑을 경우가 됨
2. nums1에서 i를 뽑았을 때 존재할 수 있는 maxSequence와 nums2에서 k - i개를 뽑았을 때 존재할 수 있는 MaxSequence를 병합하여 기존 최댓값과 비교한다.
3. 최댓값을 반환한다.

function maxNumber(nums1: number[], nums2: number[], k: number): number[] {
    function maxSequence(nums: number[], size: number) {
        if(size === 0) return []
        const stack = []
        let drop = nums.length - size
        for(const num of nums) {
            while(stack.length && drop > 0 && num > stack.at(-1)) {
                stack.pop()
                drop--
            }
            stack.push(num)
        }
        return stack.slice(0, size)
    }
    function merge(nums1: number[], nums2: number[]) {
        const result = []
        while(nums1.length || nums2.length) {
            if(nums1 > nums2) result.push(nums1.shift())
            else result.push(nums2.shift())
        }
        return result
    }
    let best = []
    for(let i = Math.max(0, k - nums2.length); i <= Math.min(k, nums1.length); i++) {
        const candidate = merge(maxSequence(nums1, i), maxSequence(nums2, k - i))
        if(candidate > best) best = candidate
    }
    return best
};