frontend-algo / into-the-deep

1 stars 0 forks source link

[10월] 1주차 스터디 #40

Open Choozii opened 1 year ago

intothedeep commented 1 year ago
/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
    if (nums.length === 1) return nums[0];
    if (nums.length < 3) return Math.max(nums[0], nums[1]);

    let sums = new Array(nums.length).fill(0);
    sums[0] = Math.max(nums[0], 0);
    sums[1] = Math.max(nums[1], sums[0]);
    sums[2] = Math.max(nums[2] + sums[0], sums[1]);

    for (let i = 3; i < nums.length - 1; i++) {
        const curr = nums[i];
        sums[i] = Math.max(sums[i - 2] + curr, sums[i - 1]);
        sums[i] = Math.max(sums[i], curr);
    }
    const odd = sums[nums.length - 2];
    // console.log('odd:: ', sums);

    sums = new Array(nums.length).fill(0);
    sums[0] = 0
    sums[1] = Math.max(nums[1], 0);
    for (let i = 2; i < nums.length; i++) {
        const curr = nums[i];
        sums[i] = Math.max(sums[i - 2] + curr, sums[i - 1]);
        sums[i] = Math.max(sums[i], curr);
    }    
    // console.log('even:: ', sums);

    const even = sums[nums.length - 1];

    return Math.max(odd, even);
};

// 1 5 3 1
// 3 5 3 1
// 1 2 3 4
// 4 3 2 1
// 10 1 1 1
// 1 1 1 10
// 1 10 1 1
// 1 1 10 1
Choozii commented 1 year ago
/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
  // 해당 원소를 더하거나 말거나
  // 더했다면 더한 원소의 인덱스를 넘기도록 해서 연속된 인덱스나 마지막 - 첫번째 원소가 만나지 않도록 처리

    const sums = [];

    const dfs = (sum, visited, idx) => {

        if(idx === nums.length){
            sums.push(sum);
            return;
        }

        // 이웃하는 값을 방문하지 않았다면?
        if(!visited.includes(idx - 1)){

            // 현재 마지막 원소라면
            if(idx === nums.length - 1){
                //첫번째 원소가 있는지 체크
                if(!visited.includes(0)){
                    dfs(sum+nums[idx], [...visited, idx], idx+1);
                }
            }else{
               // 해당 값을 더하는 경우
                dfs(sum+nums[idx], [...visited, idx], idx+1); 
            }
        }

        // 이미 이웃하는 값을 방문한 경우 + 해당 값을 그냥 더하지 않는 경우
        dfs(sum, [...visited], idx+1);
    }

    dfs(0, [], 0);

    return Math.max(...sums);
};
hyunahOh commented 1 year ago
/**
 * @param {number[]} nums
 * @return {number}
 */
/*
[2, 3, 2, 3]
 0, 2, 3
 2, 3, 
*/
var rob = function(nums) {
    const withoutMeArr = new Array(nums.length);
    const withMeArr = new Array(nums.length);
    let swap = false;

    for (let i=0; i<nums.length; i++) {
        if (i===0) {
            withoutMeArr[i] = 0;
            withMeArr[i] = nums[i];
        } else {
            const _swap = withoutMeArr[i-1] > withMeArr[i-1];
            withoutMeArr[i] = Math.max(withoutMeArr[i-1], withMeArr[i-1]);
            withMeArr[i] = withoutMeArr[i-1] + nums[i];

            if (_swap) {
                swap = !swap;
            }

        } 
    }

    const isOdd = !!nums.length % 2;

    return Math.max(withoutMeArr[nums.length-1], withMeArr[nums.length-1])
};
hyunahOh commented 1 year ago
var rob = function(nums) {
    const withoutMeArr = new Array(nums.length);
    const withMeArr = new Array(nums.length);
    const withoutMeArr1 = new Array(nums.length).fill(0);
    const withMeArr1 = new Array(nums.length).fill(0);
    if (nums.length === 1) {
        return nums[0]
    }
    for (let i=0; i<nums.length-1; i++) {
        if (i===0) {
            withoutMeArr[i] = 0;
            withMeArr[i] = nums[i];
        } else {
            withoutMeArr[i] = Math.max(withoutMeArr[i-1], withMeArr[i-1]);
            withMeArr[i] = withoutMeArr[i-1] + nums[i];
        } 
    }

    for (let i=1; i<nums.length; i++) {
        if (i===0) {
            withoutMeArr1[i] = 0;
            withMeArr1[i] = nums[i];
        } else {
            withoutMeArr1[i] = Math.max(withoutMeArr1[i-1], withMeArr1[i-1]);
            withMeArr1[i] = withoutMeArr1[i-1] + nums[i];
        } 
    }

    return Math.max(withoutMeArr[nums.length-2], withMeArr[nums.length-2], withoutMeArr1[nums.length-1], withMeArr1[nums.length-1])
};