input: 정수 rowIndex
output: Pascal’s Triangle을 만들었을 때, rowIndex열 리턴
• 0 <= rowIndex <= 33
Pascal's Triangle II - LeetCode
input: 정수 rowIndex
output: Pascal’s Triangle을 만들었을 때, rowIndex열 리턴
• 0 <= rowIndex <= 33
3 → [1, 2, 1]
4 → [1, 4, 4, 1]
5 → [1, 4, 6, 4, 1]
6 → [1, 5, 10, 10, 5, 1]
7 → [1, 6, 15, 20, 15, 6, 1]
처음엔 바로 해당 열을 만들 수 있는 규칙을 찾으려 했지만, 바로 값을 구할 수 있는 점화식 없이 재귀를 통한 연산이 필수적임을 깨달았다…
rowIndex 크기의 Pascal’s Triangle을 만들고 해당 열을 리턴하면 된다 → Sol1
구현
주어진 rowIndex만큼 삼각형 만들고, 해당 열 리턴
class Solution {
fun getRow(rowIndex: Int): List<Int> {
val triangle = generate(rowIndex + 1)
return triangle[rowIndex].toList()
}
fun generate(numRows: Int): Array<MutableList<Int>> {
val answer = Array<MutableList<Int>>(numRows){mutableListOf()}
for (r in 0 until numRows) {
for (c in 0..r) {
if (c == 0 || c == r) {
answer[r].add(1)
} else {
answer[r].add(answer[r - 1][c - 1] + answer[r - 1][c])
}
}
}
return answer
}
}
시간 복잡도: 배열 순회 = n^2
