[리트코드 (LeetCode)] Pascal's Triangle (Python)

Pascal’s Triangle

• https://leetcode.com/explore/featured/card/top-interview-questions-easy/99/others/601/
• 분류: Top Interview Questions - Easy - Others

Explore - LeetCode

문제

• 주어진 정수 numRow에 대해 파스칼의 삼각형의 첫번째 numRows를 반환하라.
• type numRows: int / rtype: List[List[int]]

예시

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Input: numRows = 1
Output: [[1]]

조건

• numRows는 1~30 사이 정수

풀이

1. 2중 for문으로 i, j 인덱스를 통해 dp (바텀업, 메모이제이션)

 

파스칼의 삼각형 조건

1) 가운데 원소는 본인 위의 두 원소의 합

2) 항상 각 row의 첫/마지막 원소는 1임 → d[i][0] = d[i][-1] = 1

 

d[2][1] = d[1][0] + d[1][1]

d[3][1] = d[2][0] + d[2][1]

...

d[i][j] = d[i-1][j-1] + d[i-1][j]

 

row에 순차적으로 원소를 append 할 것인지 미리 만들고 갱신할 것인지

→ 모든 원소를 1로 초기화한 리스트를 미리 만들어두고 값을 갱신하는 식으로 하면, 입력이 1, 2인 경우도 함께 처리할 수 있지 않을까?

class Solution(object):
    def generate(self, numRows):
        pascal = []
        for i in range(1, numRows + 1):
            pascal.append([1] * i) # pascal[i][0] = pascal[i][-1] = 1
            for j in range(1, i-1):
                pascal[i-1][j] = pascal[i-2][j-1] + pascal[i-2][j]
        return pascal

Runtime: 16 ms (beats 85.42%) / Memory Usage: 13.5 MB (beats 15.78%)

 

1-2. 이중 for문을 sum/리스트 슬라이싱과 함께 사용

직전 행의 두 원소를 더하는 것을 리스트 슬라이싱과 sum 함수로 처리

def generate(self, numRows):
    num = [[1], [1, 1]]
    if numRows == 1:
        return [[1]]
    elif numRows == 2:
        return num
    elif numRows == 0:
        return []
    row = []
    for i in range(2, numRows):
        for j in range(i - 1):
            row.append(sum(num[-1][j:j + 2]))
        num.append([1] + row + [1])
        row = []
    return num

Runtime: 23 ms (beats 35.9%) / Memory Usage: 13.3 MB (beats 70.12%)

 

2. 단일 for문을 map과 함께 사용

 

직전 행에 각각 앞/뒤로 0을 더하여 만든 리스트를 서로 더하여 다음 행을 만든다는 원리

 

map의 첫 번째 인자로 lambda x, y: x+y 라는 함수를 주고, map의 두, 세 번째 인자로 해당 함수를 실행할 iterable(반복 가능한 자료형, 여기서는 리스트)를 주었음 res[-1] + [0], [0] + res[-1]

즉 res[-1]+[0]한 list와 [0]+res[-1]한 list에 대해 같은 인덱스의 원소를 서로 더해서 새로운 row(list)를 만든 후 이것을 res에 더해주었다는 것 (새로 만든 row를 append)

같은 인덱스의 원소끼리 더하는 것이므로 zip 함수를 이용한 코드도 있던데 크게 좋은지 모르겠어서 따로 가져오진 않았다.

 

* map 함수의 반환 값은 map 객체이므로 list로 변환한 후 res에 더해주어야 함

def generate(self, numRows):
        res = [[1]]
        for i in range(1, numRows):
            res += [list(map(lambda x, y: x+y, res[-1] + [0], [0] + res[-1]))]
        return res[:numRows]
"""
    1 3 3 1 0 
 +  0 1 3 3 1
 =  1 4 6 4 1
"""

Runtime: 12 ms (beats 96.73%) / Memory Usage: 13.3 MB (beats 92.43%)

 

• 참고: https://leetcode.com/explore/interview/card/top-interview-questions-easy/99/others/601/discuss/38128/Python-4-lines-short-solution-using-map