[프로그래머스 자바스크립트] ‘정수 삼각형’ 풀어보기

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

 

1. 처음 든 생각

Dynamic Programming을 활용하여 푸는 문제라는 사실을 알고 있었기 때문에 고민하는데 드는 시간이 오래 걸리지는 않았다. 삼각형 칸 하나 당 배열을 생성하고, 위 칸의 배열에 존재하는 합들을 아래 칸에 더해서, 아래 칸의 배열에 넣어주는 행위를 반복하고, 맨 밑의 칸들을 순회하면서 가장 큰 값을 찾으면 될 것 같다는 결론을 내렸다. (참고로 맨 왼쪽에 있는 칸과 맨 오른쪽에 있는 칸은 윗 줄에서 한 가지 칸의 누적합들만 받아오면 되고, 다른 칸들은 윗 줄에서 두 가지 칸의 누적합들을 더 해줘야 된다).

 

그리고 차례대로 구현을 했고, 테스트 1개를 통과해서 자신있게 코드를 제출했다.

 

---

2. 메모리 부족 코드

function solution(triangle) {
    
    const height = triangle.length;
        
    // 삼각형에 맞게 빈 배열 생성
    const dp = Array.from({length: height}, (_, i) => Array.from({length: i + 1}, () => []));
    
    // 맨 위의 값 넣기
    dp[0][0].push(triangle[0][0]);
    
    for(let i = 1; i < height; i++) {
    
        for (let j = 0; j < triangle[i].length; j++) {
            if(j === 0) {
                dp[i-1][0].forEach((element) => {
                    dp[i][0].push(element + triangle[i][0]);
                })
            }
            else if (j === triangle[i].length - 1) {
                dp[i-1][dp[i-1].length - 1].forEach((element) => {
                    dp[i][dp[i].length - 1].push(element + triangle[i][triangle[i].length - 1]);
                })
            }
            else {
                dp[i-1][j-1].forEach((element) => {
                    dp[i][j].push(element + triangle[i][j]);
                })
                
                dp[i-1][j].forEach((element) => {
                    dp[i][j].push(element + triangle[i][j]);
                })
                
                
            }
        }
    }
    
    const answerArray = [];
    
    const bottomLength = triangle[height - 1].length;
    
    for(let i = 0; i < bottomLength; i++) {
        dp[height-1][i].forEach((element) => {
            answerArray.push(element);
        })
    }
    
    return Math.max(...answerArray);
}

 

 

하지만 테스트를 통과하지 못하였다. 실패 옆에 뜬 signal: aborted (core dumped)는 무슨 뜻일까 검색해보니 메모리가 부족하다는 뜻이었다. 생각해보니 삼각형의 한 칸마다 빈 배열을 만들고, 위에서부터 누적된 합들을 전부 저장하는 것은 효율적이지 않은 방식이었다. 어떻게 하면 메모리를 덜 잡아먹는 효율적인 코드를 만들 수 있을까?

 

---

3. 이번에는 시간 초과

생각해보니 모든 누적된 합들을 저장할 필요는 없었다. 누적된 합들을 비교해서 가장 큰 값만 받아와서 더해주면, 각 칸들에는 최댓값 한 개만 저장이 되므로 메모리가 초과되지 않을 것 같았다. 그래서 Math.max를 활용해서 최댓값만 저장했다.

 

function solution(triangle) {
    
    const height = triangle.length;
        
    // 삼각형에 맞게 빈 배열 생성
    const dp = Array.from({length: height}, (_, i) => Array.from({length: i + 1}, () => []));
    
    // 맨 위의 값 넣기
    dp[0][0].push(triangle[0][0]);
    
    for(let i = 1; i < height; i++) {
    
        for (let j = 0; j < triangle[i].length; j++) {
            if(j === 0) {
                const tempArray_1 = [];

                dp[i-1][0].forEach((element) => {
                    tempArray_1.push(element + triangle[i][0]);
                })

                const max_1 = Math.max(...tempArray_1);
                dp[i][0].push(max_1);
                
            }
            else if (j === triangle[i].length - 1) {
                const tempArray_2 = [];
                
                dp[i-1][dp[i-1].length - 1].forEach((element) => {
                    tempArray_2.push(element + triangle[i][triangle[i].length - 1]);
                });
                
                const max_2 = Math.max(...tempArray_2);
                dp[i][dp[i].length - 1].push(max_2);
            
                
            }
            else {
                const tempArray_compare = [];
                
                const tempArray_3 = [];
    
                dp[i-1][j-1].forEach((element) => {
                    tempArray_3.push(element + triangle[i][j]);
                })
                
                const max_3 = Math.max(...tempArray_3);
                
                tempArray_compare.push(max_3);
                
                const tempArray_4 = [];
                
                dp[i-1][j].forEach((element) => {
                    tempArray_4.push(element + triangle[i][j]);
                })
                
                const max_4 = Math.max(...tempArray_4);
                
                tempArray_compare.push(max_4);
                
                const max_compare = Math.max(...tempArray_compare);
                
                dp[i][j].push(max_compare);
            }
        }
    }
    
    const answerArray = [];
    
    const bottomLength = triangle[height - 1].length;
    
    for(let i = 0; i < bottomLength; i++) {
        dp[height-1][i].forEach((element) => {
            answerArray.push(element);
        })
    }
    
    return Math.max(...answerArray);
}

 

코드를 제출해보니 메모리 부족은 발생하지 않았다. 하지만 효율성 테스트에서 시간 초과가 발생했다. 어떻게 하면 시간 초과를 막을 수 있을까?

 

---

3. 드디어 정답

생각해보니 삼각형의 칸마다 새로 빈 배열을 만들지말고 값 하나만 넣으면 되는 일이었다. 그래서 빈 배열이 아니라 전부 0으로 초기화를 시켜주었고, 맨 왼쪽 칸과 맨 오른쪽 칸이 아닌 경우에는 위 칸의 두 가지 값만 비교해서 큰 값을 더해주었다. 이렇게 구조를 바꾸어주니 드디어 문제를 통과할 수 있었다.

function solution(triangle) {
    
    const height = triangle.length;
        
    const dp = Array.from({length: height}, (_, i) => Array.from({length: i + 1}, () => 0));
        
    // 맨 위의 값 넣기
    dp[0][0] = triangle[0][0];
    
    for(let i = 1; i < height; i++) {
    
        for (let j = 0; j < triangle[i].length; j++) {
            if(j === 0) {
                dp[i][j] = dp[i-1][j] + triangle[i][j];
            }
            else if (j === triangle[i].length - 1) {
                dp[i][dp[i].length - 1] = dp[i-1][dp[i-1].length - 1] + triangle[i][triangle[i].length - 1];
            }
            
            else {                
                dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
            }
        
        
        }
    }
    
    return Math.max(...dp[height - 1]);
}

 

 

이번 문제를 풀면서, 모든 경우의 수를 저장할 필요가 없이 최적의 값만 저장하는 것이 시간 측면에서나 메모리 측면에서 훨씬 효율적이라는 사실을 깨달았다. 또한, 불필요한 배열을 생성하는 것을 자제해야 한다는 사실도 알 수 있었다. 메모리 부족으로 통과를 못한 적이 이번이 거의 처음이었기 때문에 메모리 관리의 중요성도 알 수 있었던 기회였다.