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

문제

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

 

코딩테스트 연습 - 정수 삼각형

[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30

programmers.co.kr

 

시도 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 이하의 정수입니다.

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

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