.leetcode(118. Pascal's Triangle)

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

 

2021.12.31 시도

소요시간: 17분(6분 구상, 11분 코딩)

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<>();
        for(int x=0; x<numRows; x++) {
            List<Integer> inner = new ArrayList<>();
            for(int y=0; y<=x; y++) {
                if (y == 0) {
                    inner.add(1);    
                } else if (y == x) {
                    inner.add(1);
                } else {
                    inner.add(ret.get(x-1).get(y-1) + ret.get(x-1).get(y));
                }
            }
            ret.add(inner);
        }
        
        return ret;
    }
}

풀이 접근 과정

샘플에 나온 output을 보니 이건 어디다가 다 저장해야되는구나라는 생각이 들고 저장해야하기 때문에 output에 나온 갯수만큼 실행되겠다 싶었다. 저장 개수는 n(n+1)/2로 생각이 들었고 그러면 이 로직도 최소 시간복작도는 O(n^2)라는 생각이 들었다.

결국 덧셈이기에 다 읽으면서 실행하면 해결책이 나올것으로 보였는데 뭔가 더 쉬운 방식이 있을지 고민되었다. 하지만 5분이상 고민해도 접근이 떠오르지 않아 일단 풀어보기로 했다. 내가 안다고 생각하는 것을 실제로 구현했을 때 막히는 경우도 왕왕있기때문이다.

리스트보다 배열이 쉬울까라는 고민을 했지만 return값이 list로 나와있기때문에 리스트로 풀어보기로 했다.
리스트의 범위를 넘어가는첫번째와 마지막은 따로 분기를 태워야 전체로직에 방해가 되지 않게 일단 작성하니 가운데 로직 부분은 쉽게 풀렸다. 다만 x-1, y-1이 존재하기 때문에 오류가 나지 않을까 한번 더 로직을 살펴보았다. 결론적으로 분기에서 잘 처리가 되기때문에 위와 같은 코드로 제출하였다.

느낀점

• 스스로 푼 후에 솔루션을 확인하는데 특별한 해법이 없었다. 더 고민했다면 시간만 아까웠겠다. 일단 지금처럼 전체적으로 시간복잡도가 어느정도 예상되고 풀이가 그에 부합한다면 일단 코드를 짜보는게 도움이 되겟다.

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형