99클럽 코테 스터디 22일차 TIL (Pascal’s Triangle II) - LeetCode

말하는 감자·2024년 8월 12일

99클럽 99클럽3기 dynamic programming 다이나믹 프로그래밍 동적 프로그래밍 코딩테스트 코딩테스트 준비 파스칼 삼각형 파이썬 향해99

99클럽 3기

목록 보기

22/42

어제 문제와 거의 동일한 문제이다.

어제 문제에 대한 TIL은 아래 링크를 확인해보자!

99클럽 코테 스터디 21일차 TIL (Pascal’s Triangle)

1. 오늘의 학습 키워드

Dynamic Programming
동적 프로그래밍
pascal’s Triangle

2. 문제: 119. Pascal’s Triangle II

단계: Easy
주제: Array, Dynamic Programming
출처: https://leetcode.com/problems/pascals-triangle-ii/

문제 설명

Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle.

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

!https://upload.wikimedia.org/wikipedia/commons/0/0d/PascalTriangleAnimated2.gif

Example 1:

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

Example 2:

Input: rowIndex = 0
Output: [1]

Example 3:

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

Constraints:

0 <= rowIndex <= 33

3. 나의 풀이

접근 방법

이 문제는 어제 풀었던 pascal triangle문제와 거의 유사하다. 차이점은 어제 문제는 해당하는 rowIndex만큼 파스칼 삼각형을 만들어서 리턴하는게 문제였다면 오늘은 인자로 주어지는 rowIndex에 해당하는 파스칼 삼각형을 리턴하는것이 문제이다.

문제를 살펴보면 0부터 시작하는 인덱스임을 말하고 있다. 즉, 프로그래밍 언어에서의 인덱스와 동일한 형태라 생각하면 된다.

어제 문제는 파스칼 삼각형을 만들어야 하기때문에, 모든 값들을 저장해야 했지만 오늘은 원하는 rowIndex 에 해당하는 값만 가져오면 되기 때문에 파스칼 삼각형을 모두 만들 필요가 없다.

그래서 코드를 구현하면 다음과 같이 간단히 할 수 있다.

class Solution(object):
    def getRow(self, rowIndex):
        """
        :type rowIndex: int
        :rtype: List[int]
        """
        pascal = [1] * (rowIndex+1) # [1,1,1,1]
        # print(pascal)

        for i in range(1,rowIndex+1): # i = 1,2,3
            for j in range(i-1,0,-1): # j = (i=1, j= X), (i=2,j = 1), (i=3, j=2, 1)
                pascal[j] += pascal[j-1]

        return pascal

또한, 파스칼 삼각형을 정의하고 구하는 방법도 있다.

class Solution(object):
    def getRow(self, rowIndex):
        """
        :type rowIndex: int
        :rtype: List[int]
        """
        
        
        pascal = [[1]* (i+1) for i in range(rowIndex+1)]

        for i in range(2,rowIndex+1):
            for j in range(1,i):
                pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j]

        return pascal[rowIndex]