[LeetCode/120/Java]Triangle

[LeetCode/120/Java]Triangle

풀이

class Solution {
	/**
	 * time complexity O(N)
	 * space complexity O(N)
	 * @param triangle
	 * @return
	 */
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle.size() == 0) return 0;
        int[] temp = new int[triangle.size()];

        for (int i = 0; i < triangle.get(triangle.size() - 1).size(); i++) {
			temp[i] = triangle.get(triangle.size() - 1).get(i);
		}
        
        for (int i = triangle.size() - 2; i >= 0; i--) {
            for (int j = 0; j <= triangle.get(i).size() - 1 ; j++) {
                temp[j] = triangle.get(i).get(j) + Math.min(temp[j], temp[j + 1]);
            }
        }
        return temp[0];
    }
}

후기

※요구사항
삼각형 배열이 주어지면 위에서 아래로 최소 경로 합계를 반환합니다.
각 단계에 대해 아래 행의 인접한 번호로 이동할 수 있습니다. 보다 공식적으로, 
현재 행의 인덱스 i에 있는 경우 다음 행의 인덱스 i 또는 인덱스 i + 1로 이동할 수 있습니다.

O(n) 추가 공간만 사용하여 이 작업을 수행할 수 있습니까? 여기서 n은 삼각형의 총 행 수입니다.

※방법
마지막 인덱스부터 차례대로 올라오면서 합계가 작은 순으로 앞으로 배치하도록 풀이했습니다.
   2
  3 4
 6 5 7
4 1 8 3

(6+1)7 (5+1)6 (7+3)10
(6+3)9 (4+6)10
(9+2)11

 

처음에 재귀함수를 이용해서 풀이하였지만 재귀를 통해서 할 경우 메모리 사용 빈도가 늘어나고 타임 리미트까지 발생했기 때문에 위와 같은 방식을 이용했습니다.

 

재귀를 이용했던 방식

public class Solution {
    private Integer result = Integer.MAX_VALUE;
    
    public int minimumTotal(List<List<Integer>> triangle) {
        minimumTotal(triangle, 0, 1, triangle.get(0).get(0));
        return result;
    }
    
    public void minimumTotal(List<List<Integer>> triangle, int idx, int dept, int sum) {
        System.out.println("SUM :" + sum);
        if(triangle.size() == dept) {
            if(result > sum) {
                result = sum;
            }
        } else {
            minimumTotal(triangle, idx, dept + 1, sum + triangle.get(dept).get(idx));
            minimumTotal(triangle, idx + 1, dept + 1, sum + triangle.get(dept).get(idx + 1));
        }
    }
}