99클럽 코테 스터디 19일차 TIL + 동적계획법

Boxx-Ham·2024년 6월 7일
0

99TIL

목록 보기
11/19
post-thumbnail

1. 오늘의 문제

Pascal's Triangle

2. 문제 분석

  • 정수 : numRows
  • numRows만큼의 Pascal's triangle 2차원 리스트 반환

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

3. 문제 풀이

  1. 일단 numRows크기의 2차원 리스트를 만들어야 함
    • ArrayList를 2차원 크기로 생성
  2. 파스칼의 삼각형 분석
    • 제일 첫 번째와 제일 마지막은 1
    • 그 외는 이전 인덱스의 자기 이전 인덱스랑 자기 인덱스랑 더한 값

4. 구현 코드

import java.util.ArrayList;

class Solution {
    public List<List<Integer>> generate(int numRows) {
        // pascal 결과를 담을 2차원 ArrayList 생성
        List<List<Integer>> pascal = new ArrayList<>();

        // pascal Row의 구현을 시행하고 pascal에 넣어준다
        for (int i = 0; i < numRows; i++) {
            // Row 별로 하나의 ArrayList 만들어줌
            List<Integer> pascalRow = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                // 맨 처음 인덱스랑 제일 뒤의 인덱스는 1
                if (j == 0 || j == i) {
                    pascalRow.add(1);
                // 그 외의 인덱스는 i-1의 j-1과 j값 더하기 
                } else {
                    pascalRow.add(pascal.get(i-1).get(j-1) + pascal.get(i-1).get(j));
                }
            }
            // pascal에 하나씩 대입
            pascal.add(pascalRow);
        }
        // 완성된 pascal 리턴
        return pascal;
    }
}

5. 오늘의 회고

  • 2차원 리스트에 대해 오늘 알게 되었다.
  • 어떻게 구현해야할지 파스칼의 삼각형을 보고 고민했었는데 2차원 리스트에 대한 파악이 오늘 문제를 푸는 것에 도움을 준 것 같아 행복하다.

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL

0개의 댓글