Portfolio

문제

N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다.

원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 하고 싶습니다. 단 스티커 한 장을 뜯어내면 양쪽으로 인접해있는 스티커는 찢어져서 사용할 수 없게 됩니다.

예를 들어 위 그림에서 14가 적힌 스티커를 뜯으면 인접해있는 10, 6이 적힌 스티커는 사용할 수 없습니다. 스티커에 적힌 숫자가 배열 형태로 주어질 때, 스티커를 뜯어내어 얻을 수 있는 숫자의 합의 최댓값을 return 하는 solution 함수를 완성해 주세요. 원형의 스티커 모양을 위해 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어 있다고 간주합니다.

제한 사항

sticker는 원형으로 연결된 스티커의 각 칸에 적힌 숫자가 순서대로 들어있는 배열로, 길이(N)는 1 이상 100,000 이하입니다.

sticker의 각 원소는 스티커의 각 칸에 적힌 숫자이며, 각 칸에 적힌 숫자는 1 이상 100 이하의 자연수입니다.

원형의 스티커 모양을 위해 sticker 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어있다고 간주합니다.

풀이

은찬


const solution = (sticker) => {
    const length = sticker.length;
    const dp1 = Array(length).fill(0);
    const dp2 = Array(length).fill(0);
        
    dp1[0] = sticker[0];
    dp1[1] = sticker[0];
    dp2[1] = sticker[1];

    for(let i = 2; i < length; i++){
        if(i !== length - 1){
            dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + sticker[i]);
        } else{
            dp1[i] = dp1[i - 1];
        }
        
        dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + sticker[i]);
    }

    return Math.max(dp1[length - 1], dp2[length - 1]);
}

재영짱짱1234

시간초과


function solution(sticker) {
    if (sticker.length === 1) return sticker[0];
    if (sticker.length === 2) return Math.max(...sticker);
    const stickerLength = sticker.length;
    const dp = Array.from({length: stickerLength - 1}, () => new Array(2).fill(0));
    for (let i = 0; i < stickerLength - 1; i += 1) {
        const checkStartIndex = i;
        const checkEndIndex = i + 1;
        if (i < 2) {
            dp[i][0] = !i ? sticker[checkStartIndex] : Math.max(sticker[checkStartIndex-1], sticker[checkStartIndex]);
            dp[i][1] = !i ? sticker[checkEndIndex] : Math.max(sticker[checkEndIndex-1], sticker[checkEndIndex]);
            continue;
        }
        dp[i][0] = Math.max(sticker[checkStartIndex] + dp[i-2][0], dp[i-1][0]);
        dp[i][1] = Math.max(sticker[checkEndIndex] + dp[i-2][1], dp[i-1][1]);
    }
    return Math.max(...dp[stickerLength - 2])
}

리팩토링

2차원 배열로 1depth를 추가로 더 계산해야 하는 로직은 시간 복잡도가 추가로 더 걸림. 따라서 간단하게 1차원 배열로 푼 결과 시간 복잡도 만족.


function solution(sticker) {
    const stickerLength = sticker.length;
    if (stickerLength === 1) return sticker[0];
    if (stickerLength === 2) return Math.max(...sticker);
    const startDp = new Array(stickerLength - 1).fill(0);
    const endDp = new Array(stickerLength - 1).fill(0);
    for (let i = 0; i < stickerLength - 1; i += 1) {
        const checkStartIndex = i;
        const checkEndIndex = i + 1;
        if (i < 2) {
            startDp[i] = !i ? sticker[checkStartIndex] : Math.max(sticker[checkStartIndex-1], sticker[checkStartIndex]);
            endDp[i] = !i ? sticker[checkEndIndex] : Math.max(sticker[checkEndIndex-1], sticker[checkEndIndex]);
            continue;
        }
        startDp[i] = Math.max(sticker[checkStartIndex] + startDp[i-2], startDp[i-1]);
        endDp[i] = Math.max(sticker[checkEndIndex] + endDp[i-2], endDp[i-1]);
    }
    return Math.max(startDp[stickerLength -2], endDp[stickerLength -2])
}

효성

답 봤어요..흑흑


function solution(sticker) {
    if(sticker.length === 1) {
        return sticker[0];
    }
    const startAtFirst = takeStickerOff(sticker, 0, sticker.length-2);
    const endWithLast = takeStickerOff(sticker, 1, sticker.length-1);
    return Math.max(startAtFirst, endWithLast);
}

function takeStickerOff(sticker, firstIdx, lastIdx) {
    const memo = Array(sticker.length).fill(0);
    
    for(let i=firstIdx; i<=lastIdx; i++) {
        const prev = i>= 1 ? memo[i-1] : 0;
        const prevPrev = i>=2 ? memo[i-2] : 0;
        memo[i] = Math.max(prev, prevPrev + sticker[i]);
    }
    return memo[lastIdx];
}

스티커 모으기(2)

문제

제한 사항

풀이

시간초과

리팩토링

답 봤어요..흑흑