[LeetCode] 118. Pascal's Triangle, Easy

1. 문제

• 정수 numRows가 주어질 때, 그림과 같은 파스칼 트라이앵글을 만들어 2차원 배열로 반환하라.
• 여기서, 파스칼 트라이앵글은 문제에 들어가면 애니메이션으로 보여주지만, 위 2개의 수를 합한 수가 현재 수가 되도록 하는 것.
  • 2는 1 + 1, 3은 2+1 2+1, 4는 3+1 3+1, 6은 3+3 과 같다.

2. 풀이

function generate(numRows: number): number[][] {
	// numRows가 1과 2는 아래의 로직을 탈 필요가 없이 무조건 1로 채워진다.
    const result = [[1]];

    if(numRows === 1) return result;
    
    result.push([1,1])
    
    if(numRows === 2) return result;
    
    // numRows가 3 이상인 경우부터 이 로직을 탄다.
    for(let i = 2; i< numRows; i++) {
        const row = []; // 추가 할 Row 배열.
        for(let j = 0; j <= i; j++) { // 열의 최대 인덱스는 현재 행의 인덱스이다.
            if(j === 0 || j ===i) row.push(1);	// 처음과 마지막 인덱스는 무조건 1
            else row.push((result[i-1][j-1] + result[i-1][j])) // 그 외는 이전 행의 현재 열과 이전 열의 합.
            
        }
        result.push(row); // 결과 배열에 담아준다.
    }
    
    return result;
};

• 규칙성만 찾으면 쉬운 문제다. 문제에서 그림을 정삼각형으로 표시해서 이해하기 어려울 수 있는데, 2차원 배열에 표시해보면 알 수 있다.

1 (고정)
1 (고정)	1 (고정)
1 (고정)	2 (i-1, j-1 + i-1, j)	1 (고정)
1 (고정)	3 (i-1, j-1 + i-1, j)	3 (i-1, j-1 + i-1, j)	1 (고정)
1 (고정)	4 (i-1, j-1 + i-1, j)	6 (i-1, j-1 + i-1, j)	4 (i-1, j-1 + i-1, j)	1 (고정)

• 이렇게 표시해보면, 합 연산이 발생해야 하는 구간을 확인할 수 있다.
• 합 연산은 이전 행의 이전 열 + 현재 열 값을 더하면 된다.