LeetCode 118(Pascal's Triangle, java)

0. 문제

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

Pascal's Triangle - LeetCode

 

1. 문제 설명

- 이 문제는 배열의 길이(numRows)가 주어진다.

- 문제에서 이해를 돕기위해 그림이 주어진다.

- 그림과 같은 방식으로, 주어진 배열의 길이만큼 파스탈의 삼각형을 생성하는 것이 핵심이다. 

 

2. 문제 해설

a) 첫 번째 판단

- 우선 결과를 저장할 이중 List를 생성한다. 아래 코드에서 이를 result라는 이름으로 선언할 예정이다. 

- 그리고 이중 List 내부에 입력될 List를 생성한다. 아래 코드에서 이를 candidate 라는 이름으로 선언할 예정이다. 

- 중요한 점은 result와 candidate의 길이를 미리 선언할 수 없으므로, 크기가 가변적인 ArrayList를 구현체로 사용한다는 것이다.

 

b) 두 번째 판단

- 우선 파스칼의 삼각형은 일종의 피보나치 수열처럼 구성된다는 것을 알 수 있다.

- 그러므로 가장 첫번째 배열을 result에 직접 입력한다.

 

c) 세 번째 판단

- 문제에서 주어진 그림을 보자.

- 모든 배열의 첫번째 원소와 마지막 원소는 1이다. 이 부분은 직접 입력해주는 것이 편하다.

- 그러므로 배열을 생성하는 과정에서 잊지말고 반드시 수행한다.

 

d) 네 번째 판단

- 이제 각 배열의 원소를 어떻게 계산할 것인지 생각해보자.

 

- 문제에서 주어지는 그림을 보면, 각 배열의 원소는 다음과 같이 계산된다.

  → 첫 번째와 마지막 원소는 무조건 1이 저장된다.

  → 두번째 원소는 이전 층의 첫번째 원소와 두번째 원소의 합을 계산하여 저장한다.

  → 주어지는 numRows는 결과를 담는 result의 행의 개수이므로, 이중 for문을 사용하여 규칙을 구현한다.

 

- 파스칼의 삼각형을 계산하는데 필요한 규칙은 위의 3개가 전부다.

- 이를 코드로 풀어내면 된다. 

 

3. 정답 코드

 

class Solution {
    public List<List<Integer>> generate(int numRows) {
        
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> candidate = new ArrayList<>();
        
        candidate.add(1); // 가장 첫번째 배열을 생성한다. 즉, 첫번째 층이 된다.
        result.add(candidate); // 첫번째 층을 저장한다. 
        
        for(int i = 1; i < numRows; i++) {
            candidate = new ArrayList<>(); // 배열 초기화
            array.add(1); // 모든 배열의 첫번째 원소는 1이다. 이를 저장한다. 
            
            for(int j = 1; j < i; j++) {
                int element = result.get(i - 1).get(j - 1) + result.get(i - 1).get(j);
                array.add(element);
            }
            array.add(1); // 모든 배열의 마지막 원소는 1이다. 이를 저장한다. 
            result.add(array); // 완성된 배열을 result에 저장한다. 한개의 층이 완성된 것이다. 
        }
        return result;
    }
}

 

- 첫번째 for문이 1부터 시작하는 이유는 이미 가장 첫번째 층을 직접 입력해놓았기 때문이다.

- 두번째 for문이 1부터 시작하는 이유는 모든 층의 첫번째 원소가 무조건 1이며 이를 첫번째 for문에서 저장했기 때문이다.

- 두번째 for문에서 j < i 를 조건으로 잡은 이유는 3번째 층부터(= i가 2일 때) 저장할 원소를 계산하기 때문이다.