프로그래머스 문제풀이 (알고리즘) - 정수 삼각형

프로그래머스 문제풀이 (알고리즘) - 정수 삼각형

문제

https://programmers.co.kr/learn/courses/30/lessons/43105

시도 2 (정답)

위에서 부터 0층, 1층, 2층.. n층 이라고 할때

n층의 i번째 노드까지의 합을 node[n][i]라고 하고

n 층의 i 번째 노드까지의 최대 값을 max[n][i]라고 하면 다음과 같이 표현 가능

촤측 위 노드에서 내려온 경우 : node[n][i] = max[n-1][i-1] + node[n][i]

우측 위 노드에서 내려온 경우 : node[n][i] = max[n-1][i] + node[n][i]

예외 상황은 딱 2군데 좌, 우측 끝만 고려하면 된다.

좌측 끝 노드 값인 경우 : node[n][0] = node[n - 1][0]

우측 끝 노드 값인 경우 : node[n][n] = node[n - 1][n - 1]

다만, 나의 경우 triangle 배열을 그대로 사용하지 않았고,

n 번째 층을 탐색한다고 가정할 때 n 크기 만큼의 배열을 새로 만들어서 그 곳에 최대 값을 저장하는 방법을 택했고 아래와 같은 풀이를 작성했다.

public int solution(int[][] triangle) { int[][] max = new int[triangle.length][0]; max[0] = new int[]{triangle[0][0]}; // 1층 부터 탐색 for (int d = 1; d < triangle.length; d++) { int[] prevMax = max[d - 1]; int[] curMax = new int[triangle[d].length]; for (int i = 0; i < curMax.length; i++) { // 좌측 끝인 경우 if (i == 0) curMax[i] = prevMax[i] + triangle[d][i]; // 우측 끝인 경우 else if (i == curMax.length - 1) curMax[i] = prevMax[i - 1] + triangle[d][i]; // 선택 else curMax[i] = Math.max(prevMax[i] + triangle[d][i], prevMax[i - 1] + triangle[d][i]); } max[d] = curMax; } int result = Integer.MIN_VALUE; int[] last = max[max.length - 1]; for (int i = 0; i < last.length; i++) { if (result < last[i]) result = last[i]; } return result; }

시도 3 (정답)

이 풀이는 프로그래머스에서 다른 사람 풀이를 보고 이런 방법도 있구나 라는 것을 알게 되었다.

n 번째 층의 노드 개수는 n 이고 별도로 배열을 만들 필요 없이 주어진 triangle 에 값을 쌓으면 되기 때문에 다음과 같이 리펙토링이 가능하다.

public int solution(int[][] triangle) { // 0층이 아닌 1층 부터 탐색 for (int n = 1; n < triangle.length; n++) { // 좌측 끝 노드 triangle[n][0] += triangle[n - 1][0]; triangle[n][n] += triangle[n - 1][n - 1]; // 나머지 노드 for (int i = 1; i < triangle[n].length-1; i++) triangle[n][i] += Math.max(triangle[n - 1][i - 1], triangle[n - 1][i]); } return Arrays.stream(triangle[triangle.length - 1]).max().getAsInt(); }

시도 1 (오답)

가장 기본적인 깊이 우선 탐색

재귀 호출을 이용해서 풀어 봤다.

private Integer max = Integer.MIN_VALUE; public int solution(int[][] triangle) { dfs(triangle, 0, 0, 0); return max; } /** * 깊이 우선 탐색 * * 현재 경로로 부터 1단계 더 아래에 있는 (더 깊은) 값을 탐색 * 현재 인덱스와 같은 값 또는 1 높은 값만 탐색 * => 시간 효율이 떨어 집니다 */ public void dfs(int[][] triangle, int deep, int index, int cur) { // 마지막 => return if (deep >= triangle.length) { if (max < cur) max = cur; return; } // 다음 탐색 dfs(triangle, deep + 1, index, cur + triangle[deep][index]); dfs(triangle, deep + 1, index + 1, cur + triangle[deep][index]); }

제한사항

삼각형의 높이는 1 이상 500 이하입니다.

삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

제한사항을 보면 그닥 큰 수가 아니라서, 재귀 호출을 이용한 깊이 우선 탐색으로 문제를 풀어도 될 것이라고 생각했는데 아니었다.

모든 경우를 탐색하고, 이전의 계산 결과를 사용하지 않고 새로 계산을 하기 때문에 시간 효율이 떨어져 오답이었다.

from http://way-be-developer.tistory.com/248 by ccl(A) rewrite - 2021-08-07 21:26:46