LeetCode 알고리즘 Pascal's Triangle

오늘은 118,119 문제를 풀어보겠습니다.
모두 파스칼 삼각형 관련 문제고 난이도 Easy, Acceptance는 64.3%, 57.4%입니다.

먼저 118부터 ㄲ

정수형 numRows가 주어지면, 파스칼의 삼각형에서 첫 번째 numRows를 리턴하세요.
파스칼의 삼각형에서 각 숫자는 바로 위 두 수들을 더한 값입니다.

3번째 줄에서 2는 바로 위 1과 1를 더한 값입니다.
마지막 5번째 줄에서 6은 바로 위 3과 3을 더한 값입니다.

여기서 파스칼의 삼각형 규칙은?
첫 번째 줄은 무조건 1입니다.
각 row의 시작과 끝은 무조건 1입니다.
n번째 row에는 모두 (n)개의 수가 있습니다. (index라고 치면 n번째에 n + 1개)

주어진 예를 보겠습니다.

1번 예제
numRows로 5를 받았으면,
위 파스칼 삼각형 그림처럼 5번째 row까지 만들어서 리턴하면 됩니다.

2번 예제
numRows로 1을 받았으면 
첫 번째 row 1만 리턴해주면 됩니다.

코드

class Solution {
    func generate(_ numRows: Int) -> [[Int]] {
        var triangle = [[1]]
        if numRows == 1 { return triangle }
        
        for i in 1..<numRows {
            var row = [1]
            let prevRow = triangle[i-1]
            
            for j in 1..<prevRow.count {
                let sum = prevRow[j-1] + prevRow[j]
                row.append(sum)
            }
            
            row.append(1)
            triangle.append(row)
        }
        
        return triangle
    }
}

triangle이라는 변수를 만들어 [[1]]를 할당해줍니다.
numRows가 1이면 그냥 triangle([[1]]) 그대로 리턴해줍니다.

for 루프를 돌면서 (1부터 시작하는 이유는 triangle에 첫 번째 row를 넣어줬으니까)
새로운 row를 만들어주고 1로 할당해줬습니다. (row의 시작은 항상 1이니까)
다음 prevRow를 만들어줍니다. (이전 row의 두 수를 합쳐서 현재 row의 수를 만드는 거니까)

다음 새로운 for 루프를 만들어서 row를 채워나가는 작업을 할 겁니다.
이전 row의 두 수를 합쳐서 현재 row의 수를 만든다고 했죠?
prevRow[j-1] + prevRow[j]가 이전 row의 두 수가 됩니다.
이를 더해서 row에 붙여줍니다.

for j in 0..<prevRow.count - 1 {
    let sum = prevRow[j] + prevRow[j+1]
    row.append(sum)
}

개취지만 위와 같이 0부터 시작하고 prevRow.count - 1 전까지만 돌게 해 줘도 됩니다. 

row의 시작도 1이지만, 끝도 1이 잖아요?
그래서 마지막에 row에 1을 추가로 붙여줍니다. 
그럼 row완성!
이 row는 triangle에 붙여야죠.

실행해보니 런타임 속도가 0ms에서 10ms까지 다양하게 나오네요.
이 정도 갭은 크게 차이가 없으니 패스.

---

다음 119번 ㄲ
파스칼 삼각형 유형의 비슷한 문제입니다.

정수형 rowIndex가 주어지면, 파스칼의 삼각형에서 rowIndex번째 row를 리턴하세요. (0-indexed)
파스칼의 삼각형에서 각 숫자는 바로 위 두 수들을 더한 값입니다.

예제를 살펴보겠습니다.

이건 아까 파스칼 그림을 같이 보면 더 좋을 것 같네요.

1번 예제
rowIndex = 3
즉 4번째 row [1,3,3,1]을 리턴해주면 됩니다.

2번 예제
rowIndex = 0
즉 1번째 row [1]을 리턴해주면 됩니다.

3번 예제
rowIndex = 1
즉 2번째 row [1,1]을 리턴해주면 됩니다.

코드

class Solution {
    func getRow(_ rowIndex: Int) -> [Int] {
        var triangle = [[1]]
        if rowIndex == 0 { return triangle.last! }
                
        for i in 1...rowIndex {
            var row = [1] 
            var prevRow = triangle[i-1]
            
            for j in 1..<prevRow.count {
                let sum = prevRow[j] + prevRow[j-1]
                row.append(sum)
            }
            
            row.append(1)
            triangle.append(row)
        }
        
        return triangle.last!
    }
}

118번과 비슷하네요!
다른 점은 rowIndex에 해당하는 row를 리턴한다는 것.
for 루프를 통해 1부터 rowIndex까지만 실행하니까
즉 triangle 마지막은 항상 rowIndex니까 triangle.last! 를 리턴해주도록 했습니다.

얘도 118번과 비슷하게 런타임 결과는 0ms - 11ms 왔다 갔다 하네요.

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