5/12 금 [LeetCode #118] 파스칼의 삼각형 TIL

[LeetCode] 118. Pascal's Triangle

Pascal's Triangle - LeetCode

Can you solve this real interview question? Pascal's Triangle - 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: [https://upload.wikimedia.org/wikipedia/commons/0/0d/PascalTriangleAnimated2.gif]   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

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

나의 풀이:

// Double for loop로 풀이
function generate(numRows) {
	const result = [[1]]

	for (let i = 1; i < numRows; i++) {
		// n = 1이면 루프에 진입하지 않고 그대로 끝나게 되어 좋다.
		// n = 2: i = 1 체크 후 탈출
		// n = 3; i = 1, 2 체크 후 탈출
		// n = 5; i = 1, 2, 3, 4 체크 후 탈출
		let currentRow = [1]
		const prevRow = result[i - 1]; // n = 5: 0, 1, 2, 3
		
		for (let j = 0; j < prevRow.length - 1; j++) {
			currentRow.push(prevRow[j] + prevRow[j + 1]);
		}
		currentRow.push(1);
		
		result.push(currentRow)
	}

	return result;
}

• 이중 for문을 쓰지 않고는… 하는 방법이 없는 듯하다.

다른 풀이:

// '이전 줄'이라고 이름 붙이지 않고 그냥 i, j로 모든 층, 모든 칸을 표현한 버전. 처음에 1을 넣어두고 for 문을 나와서 끝에 1을 넣는 방식은 나와 같다.  
var generate2 = function(numRows) {
    var pascal = [];
    for (var i = 0; i < numRows; i++) {
        pascal[i] = [];
        pascal[i][0] = 1;
        for (var j = 1; j < i; j++) {
            pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j]
        }
        pascal[i][i] = 1;
    }
    return pascal;
};

// 각 줄(층)마다 크기에 맞는 빈 배열을 넣어두고, 1이 와야하는 양 끝자리 인덱스를 특정하여 if문으로 먼저 넣어주는 방식. 
var generate = function(numRows) {
    var i = 0;
    var j = 0;
    // Create an array list to store the output result...
    var res = [];
    // For generating each row of the triangle...
    for (i = 0; i < numRows; i++) {
        res.push(Array(i + 1));       // Initialize the first row of the pascal triangle as {1}...
        for (j = 0; j <= i; j++) {
            // Primary...
            if (j === 0 || j === i) {
                res[i][j] = 1;
            }
            else {
                // Calculate the elements of a row, add each pair of adjacent elements of the previous row in each step of the inner loop.
                res[i][j] = res[i - 1][j - 1] + res[i - 1][j];
            }
        }
    }
    return res;      // Return the output list of pascal values...
};

---

※ 위 내용은 스스로 공부하며 적어둔 노트이며 불확실한 내용이 있을 수 있습니다. 학습용으로 적합하지 않음을 유념해주세요. ※

Uploaded by N2T