LeetCode 118(Pascal's Triangle, Python)

1. 문제 링크

• Pascal's Triangle - LeetCode

Pascal's Triangle - LeetCode

2. 문제 설명

• 파스칼 삼각형을 알아야 함
• 파스칼 삼각형은 가장 위 꼭대기에는 1, 그 다음 줄에는 1, 1이 써있다.
• 그 다음 줄부터는 양 끝에는 1을 쓰고 그 사이에는 위에 두 수를 더해서 아래에 수를 채운다.
• 그러니까 위에 1, 1이 있으면 그 사이 아래에는 2를 쓴다. 
• 문제는 입력된 n 값이 있으면 파스칼 삼각형의 1행, 2행, ..., n행을 원소로 하는 리스트를 반환. 이때 각 행 역시 리스트임. 
• 예시) n=5 이면 [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]] 반환

3. 처음 풀이

• [1, 2, 1]에서 [1, 3, 3,1]을 만드는 과정을 생각해보면 [1, 2, 1]의 양쪽에 0을 하나씩 넣어
• [0, 1, 2, 1], [1, 2, 1, 0]을 만든 후 이 두개를 서로 대응되는 값끼리 더해주면 [1, 3, 3, 1]이 됨
• 다른 풀이보다 이 풀이가 마음에 든다. 

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        result = [[1]]
        while numRows != 1: #numRows까지 반복
            last = result[-1] #last row of pascal
            new = [x+y for x, y in zip([0]+last,last+[0])] #last 행의 앞 뒤에 0을 추가한 후 zip으로 대응되는 값끼리 packing, 이를 다시 각각 더하여 리스트로 만들기
            result.append(new)
            numRows -= 1
        return result

4. 다른 풀이

• 그냥 파스칼 삼각형 정의대로 nCr+nCr+1 = n+1 Cr+1 인 것을 인덱스 이용하여 직접 구하기

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        if numRows == 1:
            return [[1]]
        else:
            pascal = [[1], [1,1]]
            for i in range(2, numRows):
                new = [1] + [pascal[-1][j-1] + pascal[-1][j] for j in range(1, i)] + [1]
                pascal.append(new)
        return pascal

5. 배운 점

• zip을 알게된 후 스스로 유용하게 활용하여 뿌듯함.