[99클럽 코테 스터디] 22일차 TIL DP

 

 

오늘의 문제는 LeetCode

 

119. Pascal's Triangle II

 

 

문제

 

 

 

문제 설명 

정수 rowIndex가 주어지면 파스칼 삼각형의 rowIndex 번째 행을 반환하는 문제입니다. 

예를 들어 rowIndex가 3이라면, [1,3,3,1]이 반환되면 됩니다. 

 

 

문제 풀이 시간

권장 풀이 시간은 60분이었고, 저는 32분이 걸렸습니다.

 

 

 

문제 접근 방식

파스칼 삼각형의 각 행을 저장할 리스트를 선언합니다. 각 행의 첫 번째와 마지막 요소는 항상 1이기 때문에 먼저 첫 번째 요소에 1을 추가합니다. 

반복문을 사용해 이전 행의 중간 값들을 더해 새로운 값을 생성하고, 이를 현재 행에 복사합니다. 

문제를 풀 때 주의할 점은 자료형 범위 초과였습니다. 문제에서 주어진 조건에 따르면 rowIndex는 33이하의 정수이기 때문에 팩토리얼 계산을 직접 사용하거나  이항계수 계산식을 사용할 때 일정 수 보다 커지면 잘못된 값을 반환하게 됩니다. 

 

 

 

문제 풀이

import java.util.Arrays;
import java.util.ArrayList;

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

        for(int i = 1; i <= rowIndex; i++) {
            
            List<Integer> preRow = new ArrayList<>(row);

            for(int j = 1; j < i; j++) {
                preRow.set(j, row.get(j - 1) + row.get(j));
            }

            preRow.add(1);

            row = preRow;
        }

        return row; 
    }
}

 

 

factorial 메서드를 사용했을 때의 문제점

앞서 언급했듯이 rowIndex의 범위가 33이하의 정수이기 때문에 팩토리얼을 사용한 연산의 경우 자료형 범위를 초과하게 되어 스택오버플로우가 발생하게 됩니다. 첫 번째 시도 때 제약 조건을 제대로 확인하지 않고 코드를 작성해서 테스트 케이스는 통과 됐지만 제출을 했을 때 잘못된 결과가 반환되는 문제가 있었습니다. 

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

class Solution {
    public List<Integer> getRow(int rowIndex) {
        
        List<Integer> row = new ArrayList<>();
        row.add(1);
        for(int i = 1; i <= rowIndex; i++) {
            row.add(factorial(rowIndex) / (factorial(i) * factorial(rowIndex - i)));
        }

        return row;
    }

    public static int factorial(int num) {

        int result = 1;
        for(int i = 1; i <= num; i++) {
            result *= i;
        }
        return result;
    }
}

 

 

 

 

이항계수 계산식을 사용했을 때의 문제점 

이항계수 계산식을 사용해 C(n, k-1)에서 C(n, k)를 구하는 방법 역시 범위 초과로 인해 잘못된 값을 반환하는 문제가 있었습니다.

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

class Solution {
    public List<Integer> getRow(int rowIndex) {
        
        List<Integer> row = new ArrayList<>();
        row.add(1);
        
        for(int i = 1; i <= rowIndex; i++) {
            row.add((row.get(i - 1) * (rowIndex - i + 1) / i));
        }
        
        return row;
    }
}

 

 

 

 

반복문 자세히 알아보기 

각 반복에서 현재 row의 상태를 복사해 preRow 리스트를 만들고, 내부 for문을 통해 preRow의 중간 값들을 갱신합니다. 이때, 이전 행에서 바로 위의 두 요소를 더해 새로운 값을 계산합니다. 마지막으로, preRow에 1을 추가하고 이를 row로 업데이트합니다.

예를 들어, rowIndex가 3일 경우, 반복문은 row를 [1], [1, 1], [1, 2, 1], 최종적으로 [1, 3, 3, 1]로 변환하여 결과를 반환합니다.

 

 

 

내부 for문 동작 방식 

내부 for문은 j = 1부터 i -1 까지 실행됩니다. 이 루프는 newRow의 중간 요소들을 채워넣습니다. 이를 위해 row의 이전 행에서 바로 위의 두 숫자를 더해 현재 newRow의 값을 계산합니다.

 

 

 

 

 

 

 

이렇게 오늘 22일차 TIL을 작성해 보았습니다.