[릿코드/javascript] 740. Delete and Earn

문제

You are given an integer array nums. You want to maximize the number of points you get by performing the following operation any number of times:

• Pick any nums[i] and delete it to earn nums[i] points. Afterwards, you must delete every element equal to nums[i] - 1 and every element equal to nums[i] + 1.

Return the maximum number of points you can earn by applying the above operation some number of times.

 

var deleteAndEarn = function(nums) {
    //굳이 지울 필요는 없을 것 같고,,...?? 하나 선택하면 앞뒤 숫자는 전혀 못쓴다고 봐야할듯.
    //같은 숫자는 몇번이든 선택할 수 있음.
    //즉 객체로 만들고, 앞뒤 숫자 제외하고 쓸 수 있는 수들 선택하면 될것같음.
    let obj = {}
    for(let i=0;i<nums.length;i++){
        if(!obj[nums[i]]) obj[nums[i]] = 0
        obj[nums[i]]++;
    }
    let max = Math.max(...nums)
    let arr = new Array(max+1).fill(0)
    for(let key in obj){
        arr[key] = obj[key]*key
    }
    for(let i=3;i<arr.length;i++){
        arr[i]+=Math.max(arr[i-2],arr[i-3])
    }
    return Math.max(...arr)
};

해당 문제는 내가 3을 번다고 생각하면 nums안에 있는 3은 백번이 있어도 모두 쓸 수 있지만, 2와 4는 백개가 있다고해도 하나도 쓸 수 없다. 문제에서는 딜리트하라고 하지만 굳이 딜리트할 필요없이 새로운 arr을 만들어서 풀었다. 해당 arr은 arr[3]에는 3을 모두 더한 값을 넣었다. 다시 이걸 돌면서 근접한 것들은 쓸 수 없음에 유의하여 max값을 찾아냈다.

 

var deleteAndEarn = function(nums) {
    let max = Math.max(...nums)
    let arr = new Array(max+1).fill(0)
    for(let i=0;i<nums.length;i++){
        arr[nums[i]]+=nums[i];
    }
    for(let i=3;i<arr.length;i++){
        arr[i]+=Math.max(arr[i-2],arr[i-3])
    }
    return Math.max(...arr)
};

리팩토링한것. 오브젝트 굳이 필요없이 바로 배열로 만들어도 가능하다.

훨씬 빨라지고 공간도 적게 차지한다.