프로그래머스 알고리즘 (java)
정수 삼각형
코드 리뷰
같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.
조건
- 맨위 부터 아래로 내려가며 숫자를 증가시킨다.
- 마지막 까지 내려가 가장 큰 수를 반환한다.
풀이방향
현재 위치의 값을 구할 때 이전 값이 필요합니다.
그래서 저는 배열을 만들었고 이전 배열과 현재 배열을 더하는 식으로 접근 했습니다.
그러다 보니 양쪽 끝부분은 가지수가 1개이고 사이 [j] 값 은 이전 [j], [j - 1] 값을 비교해 큰 값을 더했습니다.
코드
public class EssenceTriangle {
private int answer = 0;
public int solution(int[][] triangle) {
this.answer = 0;
for (int i = 1; i < triangle.length; i++) {
int previewMax = triangle[i - 1].length;
int max = triangle[i].length;
triangle[i][0] = compareAnswer(triangle[i][0] + triangle[i - 1][0]);
for (int j = 1; j < previewMax; j++) {
int left = triangle[i - 1][j - 1];
int right = triangle[i - 1][j];
if (left > right) {
triangle[i][j] = compareAnswer( left + triangle[i][j]);
} else {
triangle[i][j] = compareAnswer( right + triangle[i][j]);
}
}
triangle[i][max - 1] = compareAnswer(triangle[i][max - 1] + triangle[i - 1][previewMax - 1]);
}
return this.answer;
}
private int compareAnswer(int newAnswer) {
if (this.answer < newAnswer) {
this.answer = newAnswer;
}
return newAnswer;
}
}
느낀점
처음엔 배열을 새롭게 만들고 풀었는데 생각해보니 triangle 배열을 그대로 사용해도 될 거라는 걸 깨닫고 리팩토링을 하였습니다.
그리고 answer 를 구할 때는
Arrays.stream(triangle[triangle.length - 1]).max().getAsInt();
와 같이 재일 큰 값을 구했지만 answer 를 class 변수로 뽑고 배열의 각 값을 구할 때 this.answer 와 비교해 answer를 바꿔 값을 출력하게 바꿨습니다.
