파스칼의 삼각형2

✏️오늘의 문제

💡나의 풀이

---

class Solution {
    public List<Integer> getRow(int rowIndex) {
       List<Integer> pascal = new ArrayList();
        pascal.add(1);
        
        if (rowIndex == 0) {
            return pascal;
        }

        long val = 1;

        for (int i = 1; i < rowIndex; ++i) {
            val = (val * (rowIndex - (i - 1))) / i;
            pascal.add((int) val);
        }

        pascal.add(1);

        return pascal;
       
    }
}

Pascal의 삼각형에서 특정 행 구하기: Java 코드 설명

Pascal의 삼각형은 조합론에서 중요한 수학적 구조로, 각 행의 값은 이항 계수로 구성됩니다. 이 글에서는 주어진 행 인덱스에 해당하는 값을 계산하는 Java 메서드를 소개합니다.

코드 개요

아래의 Java 코드는 특정 행의 값을 효율적으로 계산하여 리스트 형태로 반환하는 getRow 메서드를 구현하고 있습니다.

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> pascal = new ArrayList();
        pascal.add(1);
        
        if (rowIndex == 0) {
            return pascal;
        }

        long val = 1;

        for (int i = 1; i < rowIndex; ++i) {
            val = (val * (rowIndex - (i - 1))) / i;
            pascal.add((int) val);
        }

        pascal.add(1);

        return pascal;
    }
}

코드 설명

1. 클래스 및 메서드 정의

   • Solution 클래스 내에 getRow라는 메서드를 정의합니다. 이 메서드는 rowIndex를 입력으로 받아 해당 행의 값을 반환합니다.

2. 리스트 초기화

   • ArrayList인 pascal을 생성하고, 첫 번째 요소로 1을 추가합니다. 모든 행은 1로 시작하므로 초기값으로 추가하는 것입니다.

3. 첫 번째 행 처리

   • rowIndex가 0일 경우, 즉 첫 번째 행을 요청하는 경우에는 이미 리스트에 1이 추가되어 있으므로 그 값을 반환합니다.

4. 값 계산을 위한 변수 선언

   • long 타입의 val 변수를 선언하여 각 요소의 값을 계산하는 데 사용합니다. long을 사용하는 이유는 큰 수의 계산에서 오버플로우를 방지하기 위함입니다.

5. Pascal의 삼각형 값 계산

   • for 루프를 통해 1부터 rowIndex까지 반복하며 각 요소의 값을 계산합니다.
   • val은 조합 공식을 사용하여 업데이트되며, 이는 C(rowIndex, i)를 구하는 방식입니다. 이 과정을 통해 현재 행의 각 요소를 계산하고 리스트에 추가합니다.

6. 마지막 요소 추가

   • 모든 행은 끝에 1로 마무리되므로, 리스트의 마지막 요소로 1을 추가합니다.

7. 결과 반환

   • 최종적으로 계산된 리스트 pascal을 반환합니다.

이 코드의 장단점은 다음과 같습니다.

장점

1. 효율성

   • 이 코드는 O(n) 시간 복잡도로 작동합니다. 각 요소는 이전 요소를 기반으로 계산되므로, 빠른 성능을 제공합니다.

2. 메모리 사용 최적화

   • 모든 요소를 리스트에 저장하면서도, 필요할 때만 값을 계산하므로 메모리 사용이 효율적입니다. 불필요한 공간을 차지하지 않으며, long 타입 변수를 사용하여 큰 수의 오버플로우를 방지합니다.

3. 간결함

   • 코드가 간결하고 이해하기 쉬워, 다른 개발자들이 쉽게 읽고 수정할 수 있습니다. 불필요한 복잡성이 없어 유지보수에 용이합니다.

4. 유연성

   • 입력으로 주어진 rowIndex에 따라 동적으로 결과를 생성하므로, 다양한 행의 값을 쉽게 계산할 수 있습니다.

단점

1. long 타입 사용

   • long 타입을 사용하더라도, 매우 큰 행 인덱스에 대해서는 여전히 오버플로우가 발생할 수 있습니다. 예를 들어, rowIndex가 34 이상인 경우, 이항 계수의 값이 int 범위를 초과할 수 있습니다.

2. 리스트의 최종 크기

   • 리스트에 모든 값을 저장하므로, 메모리 사용량이 행 인덱스가 커질수록 증가합니다. 특히, 대규모 데이터 처리 시 메모리 문제를 일으킬 수 있습니다.

3. 인덱스 오류 가능성

   • for 루프의 조건이 i < rowIndex로 설정되어 있어, rowIndex가 0일 경우에는 실제로 값을 계산하지 않지만 명시적으로 처리한 후에 1을 추가함으로써 혼동할 수 있습니다. 이는 코드 이해에 있어 약간의 불명확성을 줄 수 있습니다.

💡더 효율적인 코드

개선된 코드

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<Integer> pascal = new ArrayList<>(rowIndex + 1);
        
        // 초기값 추가
        pascal.add(1);
        
        for (int i = 1; i <= rowIndex; i++) {
            // 현재 행의 마지막 요소를 추가
            pascal.add(1);
            
            // 이전 행의 값들을 기반으로 현재 행의 값을 계산
            for (int j = i - 1; j > 0; j--) {
                pascal.set(j, pascal.get(j) + pascal.get(j - 1));
            }
        }
        
        return pascal;
    }
}

더 효율적인 Pascal의 삼각형의 특정 행을 계산하는 방법은 현재 행의 값을 저장하고, 이전 값을 활용하여 계산하는 방식입니다. 아래는 메모리 사용을 최소화하고, 오버플로우를 방지하기 위해 List를 활용하는 대신 배열을 사용하는 개선된 코드입니다.

코드 설명

1. 리스트 초기화:

   • pascal 리스트를 생성하고, 초기값으로 1을 추가합니다. 이 리스트는 각 행의 값을 저장합니다.

2. 행 반복:

   • for 루프를 통해 행 인덱스에 따라 반복합니다. 각 행의 첫 번째와 마지막 요소는 항상 1이므로, 매 반복에서 1을 추가합니다.

3. 현재 행의 값 계산:

   • 내부 for 루프를 사용하여 현재 행의 값을 이전 행의 값들을 기반으로 계산합니다.
   • pascal.set(j, pascal.get(j) + pascal.get(j - 1));는 현재 인덱스의 값을 이전 두 값을 더하여 업데이트합니다. 이는 메모리를 절약하면서도 필요한 값을 계산하는 방법입니다.

효율성

• 이 코드는 여전히 O(n) 시간 복잡도를 유지하면서도, 메모리 사용을 최적화합니다. 각 행의 값을 동적으로 업데이트하므로, 전체 행을 저장할 필요가 없습니다.