프로그래머스 - 정수 삼각형 (java)

1. 문제

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

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

문제 설명

제한 사항

입출력 예

---

2. 어떻게 풀까?

• 문제에서 그림은 실제로 보면 직삼각형이다.

이런 느낌?

• 7부터 아래로 내려가면서 값을 더한다, 겹치는 칸은 더 큰 값을 할당한다.

 10은 7+3, 15는 7+8

18은 10+8, 16은 10+1와 15+1중 15+1이 더 크기 때문에 16, 15는 15+0

20은 18+2, 25는 18+7과 16+7중 18+7이 더 크기 때문에 25, 20은 16+4와 15+4중 16+4가 더 크기때문에 20, 19는 15+4 

24는 20+4, 30은 25+5, 27은 25+2, 26은 20+6, 24는 19+5

• 배열의 처음과 끝은, 대소 비교를 할 필요 없이 현재 값과 이전 행의 같은 열 값을 더한 값이다
• 그 외에는 이전 행의 같은 열과 이전 행중에서 큰 값과 더한 값이다.

---

3. 코드

테스트 코드

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.*;

import org.junit.Test;

public class SolutionTest {

  @Test
  public void test1() {
    int[][] triangle = {
        {7},
        {3, 8},
        {8, 1, 0},
        {2, 7, 4, 4},
        {4, 5, 2, 6, 5}
    };
    assertThat(new Solution().solution(triangle), is(30));
  }
}

실제 코드

import java.util.Arrays;

public class Solution {

  public int solution(int[][] triangle) {
    int[][] maxSums = init(triangle);
    for (int row = 1; row < triangle.length; row++) {
      fillFirstAndLast(maxSums, triangle, row);
      for (int j = 1; j < maxSums[row].length - 1; j++) {
        maxSums[row][j] = Math.max(maxSums[row - 1][j - 1], maxSums[row - 1][j])
            + triangle[row][j];
      }
    }
    return Arrays.stream(maxSums[maxSums.length - 1]).max().getAsInt();
  }

  private void fillFirstAndLast(int[][] maxSums, int[][] triangle, int row) {
    int first = 0;
    int last = maxSums[row].length - 1;

    maxSums[row][first] = maxSums[row - 1][first] + triangle[row][first];
    maxSums[row][last] = maxSums[row - 1][last - 1] + triangle[row][last];
  }

  private int[][] init(int[][] triangle) {
    int[][] result = new int[triangle.length][];
    for (int i = 0; i < triangle.length; i++) {
      result[i] = new int[triangle[i].length];
    }
    result[0][0] = triangle[0][0];

    return result;
  }
}

• init() 에서 배열을 생성하고 (0,0)에 triangle[0][0]을 할당한다.
• fillFirstAndLast()에서 현재 행의 처음 열과 마지막 열의 값을 할당한다.
• 그리고 그 외의 값은 이전 행의 같은 열과, 이전 열중 더 큰 값과 현재 값을 더한 값을 할당한다.

Best 코드 (내가 보기에 Best)

import java.util.Arrays;

public class BestAnswer {

  public static int solution(int[][] triangle) {
    for (int row = 1; row < triangle.length; row++) {
      triangle[row][0] += triangle[row - 1][0];
      triangle[row][row] += triangle[row - 1][row - 1];
      for (int col = 1; col < row; col++) {
        triangle[row][col] += Math.max(triangle[row - 1][col], triangle[row - 1][col - 1]);
      }
    }
    return Arrays.stream(triangle[triangle.length - 1]).max().getAsInt();
  }
}

• 굳이 새 배열을 생성하지 않고, 현재 값에 최대값을 더한 값을 할당해준다.
• triangle[row][triangle[row].length-1] 보다 triangle[row][row]가 훨씬 깔끔해 보인다.

---

4. 느낀 점

• 예전에 비슷한 문제를 풀어본 기억이 나서 쉽게 풀었다.