Pascal's Triangle - LeetCode

Problem

1. input: 정수 numRows

2. output: numRows개의 행을 가진 Pascal’s triangle 배열로 리턴

   • 1 <= numRows <= 30

Idea

파스칼 삼각형의 규칙대로 배열 채우기 → Sol1

Solution

1. 구현

   파스칼 삼각형은 정삼각형처럼 생겼지만, 배열은 직각삼각형처럼 생겼다.

   파스칼 삼각형 값 채우기 규칙

   r번째 행에서

   0, r번째 열의 값은 무조건 1

   그 외의 열에 대하여, r행 c열의 값 = r-1행 c-1열의 값 + r-1행 c열의 값

   class Solution {
       fun generate(numRows: Int): Array<MutableList<Int>> {
           val answer = Array<MutableList<Int>>(numRows){mutableListOf()}
           for (r in 0 until numRows) {
               for (c in 0..r) {
                   if (c == 0 || c == r) {
                       answer[r].add(1)
                   } else {
                       answer[r].add(answer[r - 1][c - 1] + answer[r - 1][c])
                   }
               }
           }
           return answer
       }
   }
   

   시간 복잡도: 배열 탐색 = n^2

   

Point