118. Pascal's Triangle 문제의 자바 해결 방법: 효율적인 알고리즘

문제

Problem_Link

문제해결방법

• 가능한 케이스

if startpos or endpos, add end
else currpos = lastList[prevpos+currpost]

• 필요한것= 전단계 리스트, 전단계 리스트 길이 or 현재 길이
• 조심해야 할것, list에서 add()는 기본적으로 shallow copy임.
• 즉, 모든 리스트를 돌면서 첫번째와 마지막은 무조건 1을 넣고, 아니라면 전에 넣은 리스트를 참고삼아 더해서 현재리스트에 넣으면 파스칼의 삼각형이 나온다.

시간복잡도: O(n), 공간복잡도: O(n)

https://github.com/eunhanlee/leetcode_118PascalsTriangle

import java.util.*;

class Solution {
    /**
     * 입력된 숫자만큼의 층까지 파스칼의 삼각형을 생성합니다.
     *
     * @param numRows 생성할 삼각형의 층 수
     * @return 삼각형의 각 층을 나타내는 리스트들을 담은 리스트
     */
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>(); // 파스칼의 삼각형을 담을 리스트
        List<Integer> currList = null; // 현재 층의 리스트
        List<Integer> prevList = null; // 이전 층의 리스트

        for (int i = 0; i < numRows; i++) { // 각 층에 대해 반복문 실행
            currList = new ArrayList<>(); // 현재 층의 리스트 생성
            for (int j = 0; j < (i + 1); j++) { // 현재 층의 각 요소에 대해 반복문 실행
                if (j == 0 || j == i) currList.add(1); // 첫 번째와 마지막 요소는 항상 1
                else {
                    // 이전 층에서 현재 요소를 생성하기 위한 계산
                    currList.add(prevList.get(j - 1) + prevList.get(j)); 
                }
            }
            prevList = currList; // 이전 층의 리스트를 현재 층의 리스트로 설정
            result.add(currList); // 현재 층의 리스트를 결과 리스트에 추가
        }

        return result; // 생성된 파스칼의 삼각형 반환
    }

}

설명

• list를 미리 선언 해서 한다면, 아래와 같이 딥카피를 해서 해야 함.

//            prevList.clear();
//            prevList.addAll(currList);
//            result.add(List.copyOf(currList));
//            currList.clear();