[LeetCode] Pascal's Triangle II - 자바스크립트 풀이

 

1. 접근 방법

 

(1) 구하고자 하는 rowIndex의 각 원소의 값을 구하려면 이전 rowIndex의 각 원소의 값이 필요하기 때문에 통째로 삼각형을 만들어주면 된다.

 

(2) n번째 줄의 각 원소는 다음과 같이 구성돼 있다. 인덱스 0은 1, 인덱스 1~n-1는 n-1번째 줄의 인접한 왼쪽, 오른쪽 원소를 더한 값, 인덱스 n은 1이다.

파스칼의 삼각형

(3) (2)번의 내용을 이중 for문을 이용해 만들어준다.

    row.push(1);
    for (let i = 1; i <= rowIndex; i++) {
        // 이전 row의 길이보다 1 작은 숫자 만큼 for문을 돈다. 맨 마지막은 1임.
        for (let j = row.length - 1; j > 0; j--) {
            row[j] = row[j - 1] + row[j];
        }
        // 맨 마지막은 직접 넣어준다. i = 1인 경우 j for문은 타지 않음. 
        row.push(1);
    }

 

(4) 중첩된 j for문에서 j를 거꾸로 감소시키는 이유는 j for문에서 하나씩 업데이트되는 숫자와 다음 턴을 돌 때의 숫자가 서로 영향을 미치지 않게 하기 위해서다. 

자기 자신 + 자기 자신의 이전 인덱스를 더하는데 오름차순으로 연산을 하면 row = [1, 3, 3, 1]이 아니라, row = [1, 3, 4, 1]이 될 것이다.

 

2. 전체 해답

/**
 * @param {number} rowIndex
 * @return {number[]}
 */
var getRow = function(rowIndex) {
    let row = [];
    
    row.push(1); // [1]
    
    for (let i = 1; i <= rowIndex; i++) {
        
        // 이전 row의 길이보다 1 작은 숫자 만큼 for문을 돈다. 맨 마지막은 1임.
        for (let j = row.length - 1; j > 0; j--) {
            row[j] = row[j - 1] + row[j];
        }
        // 맨 마지막은 직접 넣어준다. i = 1인 경우 j for문은 타지 않음. 
        row.push(1);
    }
    
    return row;
};