119. Pascal's Triangle II

문제 설명

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?

문제 풀이

118. Pascal's Triangle 문제에서 이렇게 얘기했는데...

놀랍게도 진짜 그 문제가 나왔고, 생각보다 메모리는 빡빡하게 쓰지 않았다..
파스칼의 삼각형 문제와 동일한데, 지난 로그를 다 저장하는 것이 아니기 때문에 계속해서 이전 row를 업데이트 해 가면서 현재 row를 계산하면 된다.
위의 포스팅에서는 [0]을 붙인 다음에 계산해줬는데, 다시 생각하니까 list comprehension으로 간단하게 풀 수 있어서 개선을 해 주었다.

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        past_row, curr_row = [1], [1]
        
        for _ in range(1, rowIndex+1):
            curr_row = [past_row[i]+past_row[i+1] for i in range(len(past_row)-1)] # 상단 좌 / 상단 우 원소를 더해줌.
            # 좌우에는 1 .... 1
            curr_row = [1] + curr_row + [1]
            past_row = curr_row
        
        return curr_row```