[LeetCode/Python] 6/21 Pascal’s Triangle 문제 풀이

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

Pascal's Triangle - LeetCode

1. 문제 Summary
numRows가 주어졌을 때, Pascal Triangle이 배열 형식으로 출력되도록 하세요.
Input : numRows = 5
Output : [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
시각적인 설명은 위의 사이트에 잘 나와있다.

2. 문제 풀이
Solution은 Dynamic Programming을 사용도록 나와있었는데, 되는대로 풀려다 보니까 근본 없는 코드가 되었지만 통과는 되었다.
이전 Row의 결과를 참고하기 위해 만들어 놓은 temp2를 단순히 temp2=temp 로 두었다가 단순한 얕은 복사가 되어버려 값이 최종 결과가 모든 배열이 numRows의 결과로 채워져 버렸다. [[1,2,1],[1,2,1],[1,2,1]] 이런식으로..
내부 주소들까지 새롭게 복사되는 deepcopy를 이용해서 해결했지만.. 근본이 없어보인다!

# ===============================================
class Solution(object):
    def generate(self, numRows):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        result = []
        temp = []
        temp2 = []
        for i in range(0,numRows):
            temp2 = copy.deepcopy(temp) # 이전 Row를 참고하기 위함
            
            if i==0:
                temp.append(1)
            elif i==1:
                temp.append(1)
            else:
                temp=[]
                temp.append(1)
                for j in range(1,i):
                    temp.append(temp2[j-1]+temp2[j])
                temp.append(1)
            
            temp3 = copy.deepcopy(temp)
            
            result.append(temp3)
            
        return result
# =================END===================

무슨 알고리즘을 적용해야하고 사용해야하는지에 대해서 먼저 생각을 해봐야겠다.
원래 근본이 없는 사람이지만.. 하나씩 풀어가면서 많이 배우기를 ㅜㅜ

3. 솔루션
https://leetcode.com/problems/pascals-triangle/solution/

Pascal's Triangle - LeetCode