Leetcode 118. Pascal's Triangle (Easy)

오늘의 Leetcode 문제는 118번 Pascal’s Triangle 이다.
난이도는 Easy. 전혀 Easy 하지 않은 것 같은데.
아래가 풀어야 할 문제이다.

우선 패턴을 분석하면 첫줄은 숫자가 한개이고 그 값은 1이다.
두번째 줄은 숫자가 두개이고 그 값은 1과 1이다.
세번째 줄은 숫자가 세개이고 그 값은 1, 2,1 이다. 여기서 2는 윗줄의 1과 1을 더한 것이다.
네번째 줄은 숫자가 네개이고 그 값은 1, 3, 3, 1 이다.
첫번째 3은 윗줄의 첫번째 값 1과 두번째 값 2을 더한 값이다.
두번째 3은 윗줄의 두번째 값 2와 세번째 값 1을 더한 값이다.
다섯번째 줄은 숫자가 다섯개이고 그 값은 1, 4, 6, 4, 1 이다.
첫번째 4는 윗줄의 첫번쨰 숫자 1과 두번째 숫자 3을 더한 값이다.
그 다음 6은 윗줄의 두번째 숫자 3과 세번째 숫자 3을 더한 값이다.
그 다음 4는 윗줄의 세번째 숫자 3과 네번째 숫자 1을 더한 값이다.

이제 패턴을 알 것 같다.
1. 줄이 늘어날 수록 숫자의 갯수는 1씩 증가한다. 첫번째 줄은 한개의 숫자가 있고 그 값은 1이다.
2. 맨 처음 값과 맨 마지막 값은 각각 1이다.
3. 나머지 값들은 윗줄의 (col -1) + 윗줄의 col 값이다. 여기서 col은 해당 숫자가 그 줄의 몇번째에 있는지를 나타내는 것이다.

그럼 각 줄의 맨 처음과 맨 마지막을 제외한 나머지의 값을 구하는 공식은 다음과 같다.

triangle[row][col] = triangle[row-1][col-1] + triangle[row-1][col]

이제 패턴과 그 패턴에 따른 해당 값을 구하는 공식을 완성했으니 코딩을 시작할 차례다.

Example 1의 Output을 보면 그 값은 이중배열이다.

아래와 같이 코딩을 하면 요구 조건을 충족할 수 있다.

class Solution {
   public List<List<Integer>> generate(int numRows) {
       List<List<Integer>> triangle = new ArrayList<>();
       triangle.add(new ArrayList<>());
       triangle.get(0).add(1);
       for(int rowNum =1; rowNum  < numRows; rowNum++) {
           List<Integer> currRow = new ArrayList<>();
           List<Integer> prevRow = triangle.get(rowNum -1);
           currRow.add(1);
           for (int col = 1; col < prevRow.size(); col++) {
               currRow.add(prevRow.get(col-1) + prevRow.get(col));
           }
           currRow.add(1);
           triangle.add(currRow);
       }
       return triangle;
   }
}

한줄 한줄 분석해 보자.

class Solution { ==> 클래스 이름은 Solution이다.
   public List<List<Integer>> generate(int numRows) { ==> 메소드 이름은 generate이다.
==> input 값으로 numRows를 받는다.
==> return 값은 List<List<Integer>>이다.  배열 갯수를 마음대로 변경할 수 있도록 하기 위해서 List를 사용한다.
==> Expected Output 값이 이중 배열이기 때문에 List 안에 또 List를 넣었다. 배열내 값의 데이터 타입은 Integer이다.

       List<List<Integer>> triangle = new ArrayList<>();
==> 결과 값을 저장할 변수를 만든다. 이 변수 이름은 triangle이다.
==> List를 사용하기 위해서는 ArrayList, LinkedList, Vector, Stack 클래스들로 인스턴스 화 할 수 있다.
==> 이 중에서 ArrayList를 생성해서 인스턴스 화 시켰다.

       triangle.add(new ArrayList<>());
==> 이중 배열이기 때문에 triangle안에 ArrayList를 add 했다.

       triangle.get(0).add(1);
==> triangle의 첫 줄에는 값 1을 hardcoding으로 집어 넣었다.

       for(int rowNum =1; rowNum  < numRows; rowNum++) {
==> 결과 값을 만들기 위해 for문을 만들었다. 이 메소드의 input 값인 numRows가 결과 값의 줄의 갯수를 의미하는 것이니, 그 갯수만큼 줄을 만들기 위해서 numRows만큼만 for 문을 돌린다.

           List<Integer> currRow = new ArrayList<>();
==> 현재의 줄을 ArrayList로 인스턴스 화 한다. 이름은 currRow

           List<Integer> prevRow = triangle.get(rowNum -1);
==> 계산을 해서 현재 Row의 각 컬럼의 값을 얻기 위해서 이전 줄의 값을 가져와야 한다. prevRow에 이전 줄의 값들을 저장한다.

           currRow.add(1);
==> 현재 줄의 첫번째 값은 항상 1이다. 이 값을 하드코딩으로 집어 넣었다.

           for (int col = 1; col < prevRow.size(); col++) {
==> 현재 줄의 첫번째 값과 마지막 값을 제외한 중간에 위치한 컬럼의 값을 구하기 위해 for문을 만들었다.
==> 이전 줄의 size보다 한개 작은 숫자 만큼 돌린다.
               currRow.add(prevRow.get(col-1) + prevRow.get(col));
==> 이 코드가 핵심이다.
==> 현재 줄의 현재 컬럼에 이전줄의 현재 컬럼 -1 의 값 + 이전줄의 현재 컬럼 값을 넣어 준다.
           }
           currRow.add(1);
==> 현재 줄의 맨 마지막에는 값 1을 하드코딩으로 넣어 준다.

           triangle.add(currRow);
==> triangle에 현재 줄의 값을 add 한다.
       }

       return triangle;
==> 이중 for 문에서 구한 결과 값을 리턴한다.
   }
}

이렇게 하면 원하는 결과를 얻을 수 있다.
참고로 첫번째 for문은 결과 값이 몇줄이 될 것인지 정하는 것이고,
두번째 for 문은 각 줄에 값들을 구하기 위해 만들어진 것이다.

약간 다른 방법으로는 아래와 같이 할 수도 있다.

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> triangle = new ArrayList<List<Integer>>();

        // Base case; first row is always [1].
        triangle.add(new ArrayList<>());
        triangle.get(0).add(1);

        for (int rowNum = 1; rowNum < numRows; rowNum++) {
            List<Integer> row = new ArrayList<>();
            List<Integer> prevRow = triangle.get(rowNum-1);

            // The first row element is always 1.
            row.add(1);
==> 여기 까지는 위와 같다.

            // Each triangle element (other than the first and last of each row)
            // is equal to the sum of the elements above-and-to-the-left and
            // above-and-to-the-right.
            for (int j = 1; j < rowNum; j++) {
==> 위 코드와 다른 것인 이 한 줄이다.
==> 두번째 for문을 rowNum보다 작을 때까지 돌린다.
==> rowNum은 두번째 줄이 1이다. (위 에서 첫번쨰 줄에는 1을 하드 코딩했고 첫번째 for문에서 그 다음 줄을 rowNum = 1 을 했기 때문이다.)
==> 그리고 두번째 for 문에서는 이 rowNum보다 작을 때까지 for문을 돌린다.
==> 그러니까 실질 적으로는 두번째 에서는 줄 -2 만큼 돌리게 된다.
==> 즉 4번째 줄은 4-2 이니까 두개의 값만 구하게 된다.
==> 요구 조건을 충족 시키는 방법이다. 위 코드와는 조금 다르지만 결과 값은 똑 같다.
                row.add(prevRow.get(j-1) + prevRow.get(j));
            }

            // The last row element is always 1.
            row.add(1);
            triangle.add(row);
        }
        return triangle;
    }
}

Python 3의 코딩은 아래와 같다.

class Solution:
    def generate(self, num_rows: int) -> List[List[int]]:
        triangle = []

        for row_num in range(num_rows):
            # The first and last row elements are always 1.
            row = [None for _ in range(row_num + 1)]
            row[0], row[-1] = 1, 1

            # Each triangle element is equal to the sum of the elements
            # above-and-to-the-left and above-and-to-the-right.
            for j in range(1, len(row) - 1):
                row[j] = triangle[row_num - 1][j - 1] + triangle[row_num - 1][j]

            triangle.append(row)

        return triangle