[프로그래머스 lv.2] 땅따먹기_by.JS

🔗 문제 링크

실패한 풀이

DFS로 접근을 했는데 테스트케이스만 성공하고 제출 시 전부 실패했다. (시간초과)
아무래도 조건이 N: 100,000이하라서 재귀로 전체 케이스를 모두 탐색하기에는 시간초과가 발생한 것 같다.

function solution(land) {
    let maxScore = 0;

    const getScore = (row, col, totalScore) => {
        // 하나의 경로를 찾았을 때의 총점 -> max보다 클 경우 max의 값을 바꿔준다.
        if (row === land.length) {
            maxScore = Math.max(maxScore, totalScore);
        } else {
            land[row].forEach((value, index) => {
                if (col !== index) {
                    getScore(row + 1, col, totalScore + value);
                }
            })
        }
    }
    
    land[0].forEach((v, i) => {
        getScore(1, i, v);
    });

    return maxScore;
}

해결

DP 문제라는 글을 보고 메모이제이션하면서 풀이를 했더니 통과했다.
과정이 잘 이해되지 않아서 그림으로 그리면서 코드를 짰다..ㅎ

메모이제이션의 핵심은 이전에 구한 값을 기억해두고 활용한다는 것이다.

1. 해당 자리까지 이동했을 때 가질 수 있는 최댓값을 넣어둘 이차원 배열을 하나 만든다.

2. 시작 행은 land의 0번째 행으로 초기화해준다.

3. 이제 다음 행부터는 다음 두 값을 더해서 각 열(maxScore의 노란색)에 넣어준다.

   • 각 열의 점수(land의 파란색)
   • 이전 행에서 가지고 올 수 있는 값들(maxScore의 파란색) 중 최댓값
     * 이때, 같은 열의 값(회색)은 가져올 수 없으므로 제외시킨다

4. 노란색칸을 채우는 과정이 메모이제이션이고, 이 과정이 끝나면 마지막 행에서 최댓값을 찾아 리턴한다.

function solution(land) {
    const maxScore = Array.from({ length: land.length }, () => new Array(4).fill(0));
    maxScore[0] = land[0];

    for (let i = 1; i < land.length; i++) {
        for (let j = 0; j < 4; j++) { 
            maxScore[i][j] = land[i][j] + Math.max(...maxScore[i - 1].filter((_, index) => index !== j));
        }
    }

    return Math.max(...maxScore[maxScore.length - 1]);
}

결론

결과적으로 코드도 엄청 짧아지고, 매번 모든 칸을 방문해가며 경우의 수를 찾지 않아도 된다는 점에서 시간도 단축시킬 수 있었다.
재귀로 시간초과가 나는 경우에 유용한 개념!