[프로그래머스] 정수 삼각형 (Lv.3)
문제
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
위와 같은 삼각형 배열의 꼭대기에서 바닥까지 경로 중 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 한다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능하다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능하다.
삼각형의 정수들이 담긴 배열 triangle이 매개변수로 주어질 때 거쳐간 숫자의 최댓값을 return 하는 메서드를 완성하라.
나의 답안
최근 싸피 준비를 하며 알고리즘 공부를 하고 있다.
우선 종이로 풀어봤을 때,
상단 좌 우 칸의 누적값 중 더 큰 값과 더했을 때 최대값이 될 것이다.
빨간 펜이 최대 누적값임.
class Solution {
public int solution(int[][] triangle) {
int[][] dt = new int[triangle.length][];
dt[0] = new int[]{triangle[0][0]};
int answer = 0;
for (int i=1; i<triangle.length; i++) {
dt[i] = new int[i + 1];
for (int j=0; j<=i; j++) {
int base = triangle[i][j];
int l = j-1 >= 0 ? dt[i-1][j-1] : 0;
int r = j!=i ? dt[i-1][j] : 0;
dt[i][j] = Math.max(base + l, base + r);
if (answer < dt[i][j]) {
answer = dt[i][j];
}
}
}
return answer;
}
}
모범 답안
import java.util.*;
class Solution {
public int solution(int[][] triangle) {
for (int i = 1; i < triangle.length; i++) {
triangle[i][0] += triangle[i-1][0];
triangle[i][i] += triangle[i-1][i-1];
for (int j = 1; j < i; j++)
triangle[i][j] += Math.max(triangle[i-1][j-1], triangle[i-1][j]);
}
return Arrays.stream(triangle[triangle.length-1]).max().getAsInt();
}
}
- 별도의 누적합을 담는 배열을 별도로 생성하지 않고, triangle 배열에 누적합으로 수정 입력
- 삼각형 모서리 부분 누적합을 먼저 처리하여 불필요한 삼항연산자 사용 방지
내 답안과 구조는 비슷했지만,
훨씬 더 효율적이고 가독성이 좋은 답안이었다.
이런 아이디어를 만드는 것에 더 신경써야겠다.
복습
2차원배열 선언 시에는 각 행에 대해 배열을 각각 초기화해주어야 한다!
int[][] dt = new int[3][];
dt[0] = new int[]{2}; // 각 행의 크기를 적절히 초기화
dt[1] = new int[]{2,3};
dt[2] = new int[]{2,3,4};