Daily Leetcoding Challenge 118. Pascal's Triangle

오늘도 리트코드 챌린지로 하루 시작하기

https://leetcode.com/problems/pascals-triangle

Pascal's Triangle - LeetCode

직관

문제 자체가 직관적이기 때문에 문제 설명을 그대로 가져왔다. 현재 행의 원소 값은 이전 행의 인접한 두 원소의 합이 된다.

leetcode pascal's triangle

접근법

결과를 저장할 리스트 ret에 첫 번째 행 [1]을 넣고 초기화한다.

i=2부터 i=numRows까지 다음을 반복한다

  - 새로운 행을 저장할 newRow를 초기화한다

  - 새로운 행의 원소 개수 i개만큼 반복문을 돌면서

  - j == 0 인 경우 newRow[j] = prev[0]

  - j == i - 1인 경우 newRow[j] = prev[prev.size()-1]

  - 나머지는 newRow[j] = prev[j-1] + prev[j]

복잡도

첫 번째 행의 원소는 1개, n번째 행의 원소는 n개라서 1 + 2 + ... + n = n*(n+1)/2 회 연산이 필요하다. 따라서 시간 복잡도는 O(n^2). 공간 복잡도는 정답을 리턴하는 리스트 O(n^2)를 제외하면 O(1)로 볼 수 있다.

코드

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<>();
        ret.add(Arrays.asList(1));
        for(int i=2; i<=numRows; i++) {
            List<Integer> prev = ret.get(ret.size()-1);
            List<Integer> newRow = new ArrayList<>();
            for(int j=0; j<i; j++) {
                if (j==0) {
                    newRow.add(prev.get(j));
                } else if (j == i-1) {
                    newRow.add(prev.get(prev.size()-1));
                } else {
                    newRow.add(prev.get(j-1) + prev.get(j));
                }
            }
            ret.add(newRow);
        }
        return ret;
    }
}