99클럽 코테 스터디 22일차 TIL: Pascal's triangle

Marin·2024년 8월 12일
0

TIL

목록 보기
16/17
post-thumbnail
post-custom-banner

1 | 21일차 문제

1. Pascal's triangle

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]]

2. 풀이

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

class Solution {
    public List<List<Integer>> generate(int numRows) {
        // 파스칼 삼각형은 리스트를 요소로 가지는 2차원 리스트
        List<List<Integer>> triangle = new ArrayList<>();

        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>();
            
            // 첫 요소 1 추가
            row.add(1);

            // 가운데 요소 구하기: 이전 row의 j-1, j번째 요소의 합
            for (int j = 1; j < i; j++) {
                int value = triangle.get(i - 1).get(j - 1) + triangle.get(i - 1).get(j);
                row.add(value);
            }

            // 마지막 요소 1 추가
            if (i > 0) {
                row.add(1);
            }

            triangle.add(row);
        }

        return triangle;
    }
}
  1. 일단 2차원 리스트를 처음 사용해봐서 재밌었다.
  2. row별 첫번째, 마지막 요소는 1이라는 것
  3. 가장 어려웠던 설계는 가운데 요소가 이전 row의 j-1, j번째 요소의 합이라는 것-> 이것을 위해 j = 1 부터 시작, j < i라는 조건을 생각하는게 중요했다.

2 | 22일차 문제

1. Pascal's Triangle II

Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:


Example 1:

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

Example 2

Input: rowIndex = 0
Output: [1]

Example 3<:/br>
Input: rowIndex = 1
Output: [1,1]

2. 풀이

import java.util.*;

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<List<Integer>> triangle = new ArrayList<>();
        
        for(int i = 0; i <= rowIndex; i++) {
            List<Integer> row = new ArrayList<>();
            
            row.add(1);

            for(int j = 1; j < i; j++) {
                int val = triangle.get(i - 1).get(j - 1) + triangle.get(i - 1).get(j);
                row.add(val);
            }

            if(i > 0) {
                row.add(1);
            }

            triangle.add(row);
        }

        return triangle.get(rowIndex);
    }
}

사실 21일차 문제에서 구하는 답만 다르지 논리는 같아서 문제가 없었다.
그치만 성급하게 rowIndex를 row의 수라고 생각하는 우범을 저지름...
예제까지 다 읽고 문제 풀자.

3. 회고

지난 주 휴가를 다녀와서 나태해졌다...🥲
한 번 풀어지는 것보다 다시 일상으로 돌아오는 걸 힘들어해서 문제다.
다시 열심히 해보자.

profile
대학생 | BE | 취준 | 습관이 나를 만든다
post-custom-banner

0개의 댓글