[DP]99클럽 코테 스터디 20일차 TIL + 0119-pascals-triangle-ii

 

119. Pascal's Triangle II

Easy

---

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:

 

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

 

Follow up: Could you optimize your algorithm to use only O(rowIndex) extra space?

 

 

<내코드>

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        if rowIndex == 0 or rowIndex == 1 :           
            output = [1] * (rowIndex + 1)
            return output

        output = [1] * (2)
        for i in range(2, rowIndex + 1):
            newList = [1] * (i + 1)
            print(newList)

            for j in range(1,i):
                newList[j] = output[j-1] + output[j]
                print(newList)
            output = newList

        return output

- 지금 DP 방식이 아닌 2중반복문을 사용함 수정이 필요함

=> 문제를 알아보니 이 문제의 핵심은 시간효율성이 아니라 공간효율성임

 

- 최종적으로 필요한건 마지막 부분의 리스트 임

=> 하나씩 크기가 늘려지는 리스트 출력할 필요없음

 

<모범사례>

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        row = [1] * (rowIndex + 1)  # 1로 채워진 초기 행

        for i in range(1, rowIndex):
            for j in range(i, 0, -1):  # 뒤에서부터 앞으로 값 갱신
                row[j] += row[j - 1]

        return row

- 처음부터 최종적으로 리턴할 리스트의 크기로 초기화 가능!!!

 

- 뒤에서 부터 채우면 쉬워짐

=> 이전 값 보존을 하면서 이용이 가능해지기 때문임

 

<보충학습>

nums = [1, 2, 3, 4]
num = 0

for i in range(len(nums) - 1, -1, -1):
    num += nums[i]
    nums[i] = num

print(nums)

뒤에서 부터 누적하는 방식 학습하기