LeetCode - 파스칼의 삼각형 II

문제 설명

정수 rowIndex가 주어지면 파스칼 삼각형의 rowIndexth(0-인덱스) 행을 반환합니다.

파스칼의 삼각형에서 각 숫자는 다음과 같이 바로 위에 있는 두 숫자의 합입니다.

문제 진술 출처: https://leetcode.com/problems/pascals-triangle-ii



예 1:

Input: rowIndex = 3
Output: [1, 3, 3, 1]

예 2:

Input: rowIndex = 0
Output: [1]

예 3:

Input: rowIndex = 1
Output: [1, 1]

제약:

0 <= rowIndex <= 33

설명

파스칼 삼각형을 생성하고 행을 반환합니다.

문제는 Pascals Triangle 을 생성한 이전 블로그와 거의 유사합니다.
여기서 삼각형을 생성하는 대신 삼각형의 특정 행을 반환해야 합니다.

Pascals Triangle 블로그에 언급된 세 번째 접근 방식을 사용하고 rowIndexth를 반환할 수 있습니다.

이 접근 방식의 시간 복잡도는 O(N^2)이고 공간 복잡도는 O(1)입니다.

O(N) 솔루션

위의 접근 방식을 주의 깊게 관찰하면 전체 파스칼 삼각형을 생성하고 계수를 직접 계산할 필요가 없습니다.

더 잘 이해하기 위해 알고리즘으로 넘어갑시다.

- initialize result array

- set c = 1

  // push c into result
  result.push(c)

- loop for i = 1; i <= rowIndex; i++
  // generate the coefficient using the below formula
  - c = c * (rowIndex + 1 - i) / i

  // push the generated coefficient in the result
  - result.push(c)

- return result

이 접근법의 시간 복잡도는 O(N)이고 공간 복잡도는 O(1)입니다.

C++, Golang, Javascript에서 알고리즘을 확인해 봅시다.

C++ 솔루션

class Solution {
public:
    vector<int> pascalRow(int rowIndex) {
        vector<int> result;

        long int c = 1;
        result.push_back(c);

        for(int i = 1; i <= rowIndex; i++) {
            c = c*(rowIndex + 1 - i)/i;
            result.push_back(c);
        }

        return result;
    }

    vector<int> getRow(int rowIndex) {
        return pascalRow(rowIndex);
    }
};

골랑 솔루션

func pascalRow(rowIndex int) []int {
    result := make([]int, rowIndex + 1)
    c := 1

    result[0] = c

    for i := 1; i <= rowIndex; i++ {
        c = c*(rowIndex + 1 - i)/i
        result[i] = c
    }

    return result
}

func getRow(rowIndex int) []int {
    return pascalRow(rowIndex)
}

자바스크립트 솔루션

var pascalRow = function(rowIndex) {
    let result = [];
    let c = 1;

    result.push(c);

    for(let i = 1; i <= rowIndex; i++) {
        c = c*(rowIndex + 1 - i)/i;
        result.push(c);
    }

    return result;
}

var getRow = function(rowIndex) {
    return pascalRow(rowIndex);
};

예제 1의 알고리즘을 시험 실행해 보겠습니다.

Input: rowIndex = 3

Step 1: vector<int> result
        int c = 1

Step 2: result.push_back(c)
        result = [1]

Step 3: loop for i = 1; i <= rowIndex
        1 <= 3
        true

        c = c * (rowIndex + 1 - i) / i
          = 1 * (3 + 1 - 1) / 1
          = 1 * 3
          = 3

        result.push_back(c)
        result = [1, 3]

        i++
        i = 2

Step 4: loop for i <= rowIndex
        2 <= 3
        true

        c = c * (rowIndex + 1 - i) / i
          = 3 * (3 + 1 - 2) / 2
          = 3 * 1
          = 3

        result.push_back(c)
        result = [1, 3, 3]

        i++
        i = 3

Step 5: loop for i <= rowIndex
        3 <= 3
        true

        c = c * (rowIndex + 1 - i) / i
          = 3 * (3 + 1 - 3) / 3
          = 3 * 1 / 3
          = 1

        result.push_back(c)
        result = [1, 3, 3, 1]

        i++
        i = 4

Step 6: loop for i <= rowIndex
        4 <= 3
        false

Step 7: return result

We return the result as [1, 3, 3, 1].