LeetCode Pascal's Triangle (JavaScript)

링크 : https://leetcode.com/problems/pascals-triangle/description/

문제 설명

Given an integer numRows, return the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1
Output: [[1]]

Constraints:

• 1 <= numRows <= 30

---

문제 풀이

1. numRows + 1 * numRows + 1만큼의 배열을 만들어 각 행을 돌면서 계산

-> arr[y][x] = arr[y - 1][x] + arr[y - 1][x - 1]로 계산

-> 일단 numRows + 1만큼의 2차원 배열을 생성하고 n^2의 시간 복잡도로 해결이 가능.

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function(numRows) {
    let arr = Array.from({length: numRows + 1}, () => Array.from({length: numRows + 1}, () => 0));

    arr[1][1] = 1;

    for (let i = 2; i <= numRows; i++) {
        for (let j = 1; j <= numRows; j++) {
            arr[i][j] = arr[i - 1][j] + arr[i - 1][j - 1];
        }
    }

    return arr.slice(1).map(a => a.filter(Boolean));
};

2. 위의 알고리즘을 좀 더 효율적으로 해결

tmp는 다음 행을 계산할 데이터, 이전 행 값(answer[answer.length - 1])을 기준으로 계산 (앞 뒤로 0이 필요)

e.g. 2번째 행 계산인 경우

tmp = [0, 1, 0] -> 다음 행은 [1, 1]이 나와야 함

즉, tmp의 길이 - 1만큼 반복하면서 (위의 예시에서는 2번) j번째 + j + 1번째를 더해주면 됨.

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function(numRows) {
    const answer = [[1]];

    for (let i = 0; i < numRows - 1; i++) {
        const tmp = [0, ...answer[answer.length - 1], 0];
        const item = [];

        for (let j = 0; j < tmp.length - 1; j++) {
            item.push(tmp[j] + tmp[j + 1]);
        }

        answer.push(item);
    }

    return answer;
};

---

결론

배열을 생성해서 쉽게 해결할 수 있지만 좀 더 효율적인 방법을 생각해보는 것이 포인트인 것 같다.