[LeetCode/119/Java]Pascal's Triangle II

[LeetCode/119/Java]Pascal's Triangle II

 

풀이

class Solution {
    public static Map<Integer,List<Integer>> buf = new HashMap<Integer,List<Integer>>();
    public static int maxRow = 0;
    
    public List<Integer> getRow(int rowIndex) {
        List<Integer> prev = null;
        List<Integer> result = new ArrayList<Integer>();
        int start = maxRow;
        if(buf.containsKey(rowIndex)) return buf.get(rowIndex);
        result.add(1);

        for (int i = start; i <= rowIndex; i++) {
            prev = result;
            result = new ArrayList<Integer>();
            result.add(1);
            if(i > 0) {
                if(i > 1) result.add(i);
                if(buf.containsKey(i)) {
                    result = buf.get(i);
                } else {
                    int idx = i % 2 == 0 ? (i / 2) + 1 : (i + 1) / 2;
                    for (int j = 2; j < idx; j++) {
                        if(i % 2 == 1) {
                            result.add(prev.get(j - 1) + prev.get(j));
                        } else {
                            if(j == idx - 1) {
                                result.add(prev.get(j - 1) + prev.get(j - 1));
                            } else if(j < idx) {
                                result.add(prev.get(j - 1) + prev.get(j));
                            }
                        }
                    }
                    for (int j = result.size() - 1; j >= 0; j--) {
                        if(i % 2 == 0 && j == result.size() - 1) continue;
                        result.add(result.get(j));
                    }
                }
                buf.put(i, result);
                if(maxRow < rowIndex) maxRow = rowIndex;
            }
        }
        return result;
    }
}

후기

파스칼의 삼각형 알고리즘입니다.

기본 부르트 포스 방식을 사용하였고

메모이제이션 방식을 사용하기 위해 처리 결과를 버퍼에 담아놓고

반복적인 호출이 들어올때 값을 버퍼에서 꺼내서 사용하도록 하였습니다.

 

파스칼의 삼각형은 좌우가 대칭형식으로 되어있기 때문에

row가 짝수일 경우에는 좌측 절반만

row가 홀수일 경우에는 좌측 절반 + 중앙을 계산하는 방식을 사용했습니다.

time complexity O(N^2)
space complexity O(N^2)