Leetcode Pascal's Triangle II 파이썬 풀이

요즘에는 개발자들이 회사에 취업하기 위해서 사용한다는 리트코드 (leetcode) 사이트의 문제들을 풀어보고 있습니다. 이제 막 시작한 초보자라 힘든 점이 많아서 이렇게 글로 남겨서 복습하려고 합니다.

 

문제: Pascal's Triangle II
등급: Easy

<풀이 과정>

알아낸 점으로는, 

 

구하고자 하는 row의 전 row가 모두 쓰인다는 점이다. 그 전 row의 (i-1, j-1)이 사용된다. 이 점을 활용할수 있지 않을까?

 

어떻게든 재귀 호출의 방식을 사용하고 싶었다. 어떻게 list를 더하는 방식으로 되지 않을까 생각했는데, 음.. 

 

base case를 어떻게 정해야 하나? 

if rowindex == 0: return [1]이랑 if rowindex == 1: return [1,1]는 맞을 것 같긴한데...

 

그런 다음, return [1] + self.getRow(rowindex-1) +[1]식으로 뭔가 하면 될 것 같은데...

 

그래서, 최선을 다해서 나온 마지막 line,

return [1] + [self.getRow(rowIndex - 1)[i] +self.getRow(rowIndex-1)[i+1] for i in range(rowIndex-1) if i+1 < rowIndex -1 ] + [1]

근데 당연히 틀렸다... ㅠ

 

그런 다음 처음 적은 코드:

class Solution(object):
    def getRow(self, rowIndex):
        if not rowIndex:
            return [1]
        
        if rowIndex == 1:
            return [1,1]
        
        middle = [self.getRow(rowIndex-1)[i] +self.getRow(rowIndex-1)[i+1] for i in range(rowIndex-1)]
        
        return [1] + middle + [1]
        """
        :type rowIndex: int
        :rtype: List[int]
        """

TIME LIMIT EXCEEDED, 자랑스럽게 하였다. 어떻게 하면 빠르게 계산하게 코딩 할 수 있을까?

 

결국에는 모르겠어서, discussion을 찾아보게 되었다.

class Solution(object):
    def getRow(self, rowIndex):
        row = [1]
        
        for i in range(rowIndex):
            row = [x + y for x, y in zip([0]+row, row+[0])]
            
        return row

이걸 보면서, 아, 이게 진정한 파스칼의 삼각형이구나 했다. 

 

우선 rowIndex == 1의 케이스는,

zip([0]+row, row+[0])이 (0,1) , (1,0)이 나옴에 따라 [1,1]이 row가 된다.

 

그리고, 만약 마지막 row = [1,2,1]이 나왔다고 가정하면, zip()은 [0,1,2,1] 그리고 [1,2,1,0]이 나오게 된다. 그럼 그대로 더하게 되면, [1,3,3,1]! 정답이 나온다.

 

어떻게 하면 이런 생각을 할 수 있을까?

 

<총평 외 comment>

 

Happy coding!

Pascal's Triangle II - LeetCode