[LeetCode | Java | Dynamic Programming 문제 풀이] 118. Pascal's Triangle - Solution with Recursive Function

99클럽 2기 | 자바 | 비기너

△ 118. Pascal's Triangle

🏷 Topic : Array Dynamic Programming Recursion

Easy

Given an integer numRows, return the first numRows of Pascal's triangle.
In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

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

Example 2:

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

Constraints:

1 <= numRows <= 30

Accepted    1.7M  |  Submissions    2.3M  |  Acceptance Rate    74.5%

---

✔ Solution with Recursive Function

import java.util.List;
import java.util.ArrayList;

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> answer = new ArrayList<>();

        if (numRows == 1) {
            List<Integer> li = new ArrayList<>();

            li.add(1);
            answer.add(li);
        } else {
            answer = generate(numRows - 1);
            List<Integer> pre = answer.get(answer.size() - 1);
            List<Integer> li = new ArrayList<>();

            li.add(1);
            for (int i = 0; i < numRows - 2; i++) {
                li.add(pre.get(i) + pre.get(i + 1));
            }
            li.add(1);

            answer.add(li);
        }

        return answer;
    }
}

채점 결과

💥 오늘 만난 문제 & 나의 시도 💦 & 해결 방법 👍

LeetCode에 업로드한 풀이(🔗Solution with Recursive Function)

int numRows를 매개변수로 받을 때,

1) 파스칼 삼각형의 각 행의 원소를 List<Integer> 객체에 담는다.
2) 첫번째행부터 numRows번째행까지의 List<Integer> 객체를
List<List<Integer>> 객체에 담아 반환한다.

이 때, 파스칼의 삼각형 안의 각 숫자는
그 숫자 바로 위에 있는 두 숫자의 합으로 나타낼 수 있다.

바로 앞 행의 연속하는 두 숫자들의 합으로 다음 행의 숫자를 계산할 수 있으므로
재귀함수를 구현하여 문제를 풀어보자.

---

1. 반환할 리스트를 담을 List<List<Integer>> 객체를 생성하자.

• 리스트는 ArrayList로 구현한다.
  List와 ArrayList를 import하자.

  import java.util.List;
  import java.util.ArrayList;

• List<List<Integer>> answer 객체를 생성

    List<List<Integer>> answer = new ArrayList<>();

2. 파스칼 삼각형의 첫번째 행은 그 위에 행이 없으므로 List<Integer> 객체에 직접 1을 추가하여 answer에 담아주자.

• 재귀함수로 파스칼 삼각형을 구현하면,
  첫번째 행은 numRows가 1일 때, answer에 담긴다.

  
  

  if (numRows == 1) {
      List<Integer> li = new ArrayList<>();
  
      li.add(1);
      answer.add(li);
  }

3. numRows가 1이 아니면 answer에 generate(numRows - 1)을 할당하자.

else {
    answer = generate(numRows - 1);
    ...
}

이 때, answer에는 파스칼 삼각형의 numRows - 1번째 행까지가 List<Integer>객체로 담겨있다.

4. answer의 마지막 인덱스에 있는 객체를 꺼내 numRows번째 행을 만들어 answer에 추가하자.

• answer의 마지막 인덱스에 있는 객체를 List<Integer> pre에 할당

  answer의 마지막 인덱스의 객체 : 파스칼 삼각형의 numRows - 1번째 행
  answer의 마지막 인덱스 : answer.size() - 1

  
  

  List<Integer> pre = answer.get(answer.size() - 1);




• 파스칼 삼각형의 numRows번째 행을 만들 li 생성

  List<Integer> li = new ArrayList<>();

파스칼 삼각형의 각 행의 첫번째 요소와 마지막 요소는 1

• li에 1(첫번째 요소)을 추가

  li.add(1);

• li의 두번째 요소(인덱스 1)부터 numRows - 1번째 요소(인덱스 numRows - 2)까지를 li에 추가
  (pre의 인접한 두 요소를 더해서 구할 수 있다. 반복문을 사용하자.)

  for (int i = 0; i < numRows - 2; i++) {
      li.add(pre.get(i) + pre.get(i + 1));
  }

• li에 마지막 인덱스의 값 1을 추가

  li.add(1);

• answer에 li(파스칼 삼각형의 numRows번째 행) 추가

  answer.add(li);

위에서 만든 재귀함수는 매개변수 numRows에 대하여
generate(numRows-1),
generate(numRows-2),
...,
generate(1)까지를 순차적으로 호출하고

generate(1)은 1이 한개 담긴 파스칼 삼각형의 첫번째 행을 answer에 담아 반환,
generate(2)에서 파스칼 삼각형의 2행을 추가하여 반환,
...,
generate(numRows)에서 파스칼 삼각형의 numRows행을 추가하여 반환

즉, 파스칼 삼각형의 1행부터 numRows행까지를 담은 answer을 반환받을 수 있다.

5. answer을 반환

return answer;

---

💬 무엇을 새롭게 알았는지

재귀함수 코드 쓰는 연습을 계속 할 수 있어서 좋았습니다.

---

🆙 Next Level

• 미들러: 🆎 1641. Count Sorted Vowel Strings
• 챌린저: △ 정수삼각형