[JAVA] LeetCode 118 - Pascal's Triangle

Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.

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

 

음수가 아닌 정수 numRows가 주어지면, 파스칼 삼각형을 만들어라.

파스칼 삼각형에서 각 숫자는 그 바로 위에 있는 두 숫자의 합이다.

 

 

 

풀이 방법

문제 그대로 2중 반복문으로 파스칼 삼각형을 만들면 된다.

핵심 풀이 방법은 다음과 같다.

1. 현재 입력해야 하는 인덱스가 라인의 양 끝일 경우 1을 입력한다.

2. 라인의 양 끝이 아닐 경우, 값을 구하기 위해 이전 라인에 있던 리스트 객체를 받아온다.

3. 받아온 리스트 객체(윗 줄)에서 이전의 인덱스(j-1)와 현재 인덱스(j) 를 합한다.

4. 합한 정수를 현재 리스트(라인)에 추가한다.

5. 이렇게 반복문을 통해 생성된 한 리스트(라인)를 최종 리스트(result) 객체에 추가한다.

 

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>();
        for(int i=0; i<numRows; i++) {
            List<Integer> list = new ArrayList<>();
            for(int j=0; j<=i; j++) {
                if(j == 0 || j == i) {
                    list.add(1);
                } else {
                    int prev = result.get(i-1).get(j-1);
                    int next = result.get(i-1).get(j);
                    list.add(prev+next);
                }
            }
            result.add(list);
        }
        return result;
    }
}