[LeetCode] Pascal's Triangle II

 

 

목차

• 문제
• 문제 풀이
  • 풀이 1 : DP
  • 풀이 2 : math
• 알게 된 내용
• 출처

문제

• 파스칼 삼각형에서 rowIndex 번째의 값을 O(rowIndex)공간만 사용하여 해결하는 문제입니다.
• 예시

  • Input: rowIndex = 3
    Output: [1,3,3,1]

  • Input: rowIndex = 0
    Output: [1]

  • Input: rowIndex = 1
    Output: [1,1]

• 제약사항
  • 0 <= rowIndex <= 33

문제 풀이

풀이 1 : DP

• 풀이
  • 이전값을 prev로 기억해두고 j번째 값을 arr[j] = arr[j]+prev로 진행합니다.
  • 이럴 경우 추가적인 공간없이 해결이 가능합니다.
  • 단, 시간 복잡도는 O(N^2)이 소요될 것입니다. 
• 코드

  • class Solution:
        def getRow(self, rowIndex: int) -> List[int]:
            arr =[]
            for i in range(rowIndex+1):
                arr.append(1)
                prev = arr[0]
                for j in range(1,i):
                    arr[j],prev=arr[j]+prev,arr[j]
            return arr

풀이 2 : math

• 풀이
  • 파스칼 삼각형의 수학적인 성질을 이용하는 것입니다.
  • O(N)만에 해결이 가능해집니다.
• 코드

  • import math
    
    class Solution:
        def getRow(self, rowIndex: int) -> List[int]:
            return [math.comb(rowIndex,i) for i in range(rowIndex+1)]

알게 된 내용

• 이항계수 성질
• 파스칼 삼각형
  • 

출처

• https://leetcode.com/explore/learn/card/array-and-string/204/conclusion/1171/