LeetCode 119(Pascal's Triangle II, Python)

1. 문제 링크

• https://leetcode.com/problems/pascals-triangle-ii/

Pascal's Triangle II - LeetCode

2. 문제 설명

• rowIndex 라는 정수가 주어졌을 때, Pascal의 삼각형의 rowIndex 번째 열을 반환
  • 여기서 Pascal's 삼각형이란?
  • 아래처럼 [1,3,3,1]이 있는 열의 그 다음열에는 [1,1+3,3+3,3+1,1]인 [1,4,6,4,1]이 나와야 함

3. 처음 풀이

• 규칙 찾기가 핵심
• 우선 행의 값을 저장하는 result list를 두고, 1열에 대한 값을 [1]로 셋팅
• for 루프를 돌면서, 파스칼 삼각형의 값이 계산되는 규칙에 따라 list가 쌓이도록 구성
  • 첫번째와 마지막 element는 이전 list의 첫번째 마지막 열을 그대로 가져오고, 그 중간은 이전 list의 n번째와 n+1번째 값을 더한 값을 계산해서 append하는 구조
• rowIndex가 5이면 result를 5열까지 쌓은후, 5번째 list를 반환

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

        else:
            result = [[1]]
            for i in range(1,rowIndex+1): 
                j_list = []
                for j_index, j in enumerate(result[i-1]):
                    if j_index == 0:
                        j_list.append(j)
                    else:
                        j_list.append(result[i-1][j_index-1] + result[i-1][j_index])
                    if j_index == len(result[i-1])-1:
                        j_list.append(j)
                result.append(j_list)

            return result[rowIndex]

• runtime이 나쁘진 않았으나, 조금 더 빠르고 참신한 풀이가 있을 것 같아보였음. 지금은 문제에서 나온 규칙을 그대로 코드화 한 상태

4. 다른 풀이

• result 리스트를 [1]로 초기화 하고, 
• rowIndex가 0이 될 때까지 while문 반복
  • while문에서는 list의 앞에 0추가, list의 뒤에 0을 추가한 2개의 list의 각 element를 더하는 구조 
    • 예를 들어 result가 [1]일 때는, [0,1]과 [1,0] 두 list가 합쳐지면서 [1,1]이 되고,
    • result가 [1,1]일 때는 [0,1,1]과 [1,1,0]이 합쳐지면서 [1,2,1]이 되고, 
    • result가 [1,2,1]일 때는 [0,1,2,1]과 [1,2,1,0]이 합쳐지면서 [1,3,3,1]이 되는 구조
  • 위 규칙을 파악한 후 → 작성한 코드

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        result = [1]
        while rowIndex != 0:
            result = [x+y for x, y in zip([0]+result,result+[0])]
            rowIndex -=1
        return result

5. 배운점

• 규칙 찾기 → 하나하나 나열해보면서 규칙 파악하여 → 코드로 구현!