99클럽 코테 스터디 21일차 TIL | 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:

📝 풀이

import java.util.*;

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> pascalTriangle = new ArrayList<>();

        // 각 행을 순차적으로 생성
        for (int i = 0; i < numRows; i++) {
            // 새로운 행 생성 (1로 시작)
            List<Integer> row = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    row.add(1);
                } else {
                    row.add(pascalTriangle.get(i - 1).get(j - 1) + pascalTriangle.get(i - 1).get(j));
                }
            }
            pascalTriangle.add(row);
        }
        
        return pascalTriangle;
    }
}

문제의 포인트는 파스칼의 삼각형을 어떻게 구현하냐라고 생각한다. 파스칼의 삼각형의 첫번째 행은 항상 1이며, 각행의 첫번째와 마지막 요소도 항상 1이다. 그리고 중간 요소는 바로 위행의 두 요소의 합이라는 것. 그래서 2차원 배열을 활용하여 풀었다.

처음엔 바로 코딩을 하려다가 제대로 되지 않아서 노트에 하나씩 그려서 풀기 시작했다. 이전 행을 기반으로 현재 행을 생성할 때 첫번째 행과 마지막 행에는 1이 오게 세팅했고, 다음행의 위치에선 -1과 +1를 해서 그 위행의 요소 자리를 찾아 더해서 입력했다.

방식만 알면 생각보다 쉽게 풀 수 있는 문제!

👀 고찰

결국 파스칼의 삼각형도 재귀적 패턴이라, 어떻게 구현하면 좋을지 생각을 많이 하게 됐다.