파스칼의 삼각형 (쓰면서 익히는 알고리즘 자료구조)

1.8 파스칼의 삼각형

• 문제링크  : (5) Pascal's Triangle - LeetCode

📌 Problem

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

  

  
  
  
• 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]]
  
  • 1 <= numRows <= 30
• Constraints:
• Example 1:
• In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

📝 Solution

 

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>();
        
        if(numRows <=0){
            return result; 
        }
        
        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 left = result.get(i-1).get(j-1);
                    int right = result.get(i-1).get(j);
                    list.add(left+right);
                }
            }
            result.add(list);
        }
        return result;
    }
}

• Time complexity : O(n2)
• 기반 리스트 생성
• 1번째 리스트 요소를 1로 초기화한다
• 입력으로 주어진 행수(numRows) 만큼 순회한다.
• 항상 행의 맨 앞과 맨 뒤의 값은 1이다
• 순회하면서 해당 줄을 생성하기 위해서는 이전행의 값을 참조하여 더하거나 그대로 사용한다.