[코딩테스트] 정수 삼각형

문제

---

정수 삼각형 문제 바로가기

제출 코드(JAVA)

---

코드 제출

  class Solution {
  public int solution(int[][] triangle) {

        for (int i = triangle.length - 2; i >= 0; i--) {
            int[] layer = triangle[i];

            for (int i1 = 0; i1 < layer.length; i1++) {
                layer[i1] += Math.max(triangle[i+1][i1], triangle[i+1][i1+1]);
            }
        }

        return triangle[0][0];
    }
}

삼각형 배열의 거꾸로부터 올라갔다.
두가지 자식 노드 최대값을 부모 노드에 더하는 식으로 역순으로 올라가 최종 루트노드 반환 방식

정확성 테스트

정확성  테스트
테스트 1 〉	통과 (0.04ms, 53.1MB)
테스트 2 〉	통과 (0.04ms, 54.5MB)
테스트 3 〉	통과 (0.04ms, 52.7MB)
테스트 4 〉	통과 (0.07ms, 53.9MB)
테스트 5 〉	통과 (0.25ms, 51.8MB)
테스트 6 〉	통과 (0.10ms, 53.2MB)
테스트 7 〉	통과 (0.28ms, 52.5MB)
테스트 8 〉	통과 (0.13ms, 52.8MB)
테스트 9 〉	통과 (0.05ms, 52.9MB)
테스트 10 〉	통과 (0.08ms, 53MB)
효율성  테스트
테스트 1 〉	통과 (6.78ms, 61.4MB)
테스트 2 〉	통과 (5.81ms, 59.1MB)
테스트 3 〉	통과 (7.75ms, 61MB)
테스트 4 〉	통과 (7.05ms, 61.7MB)
테스트 5 〉	통과 (6.16ms, 58.8MB)
테스트 6 〉	통과 (8.07ms, 58.7MB)
테스트 7 〉	통과 (5.90ms, 60.3MB)
테스트 8 〉	통과 (10.26ms, 60.8MB)
테스트 9 〉	통과 (6.28ms, 61.3MB)
테스트 10 〉	통과 (6.07ms, 59.9MB)

제출 코드(Python)

---

첫번째 코드 제출

def solution(triangle):
    for i in range(len(triangle)-2, -1, -1):
        layer = triangle[i]

        for ii in range(len(layer)):
            layer[ii] += max(triangle[i+1][ii], triangle[i+1][ii+1])

    return triangle[0][0]

정확성 테스트

정확성  테스트
테스트 1 〉	통과 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.03ms, 10.2MB)
테스트 3 〉	통과 (0.06ms, 10.2MB)
테스트 4 〉	통과 (0.22ms, 10.2MB)
테스트 5 〉	통과 (1.53ms, 10.3MB)
테스트 6 〉	통과 (0.45ms, 10.3MB)
테스트 7 〉	통과 (1.46ms, 10.3MB)
테스트 8 〉	통과 (0.33ms, 10.1MB)
테스트 9 〉	통과 (0.02ms, 10.2MB)
테스트 10 〉	통과 (0.22ms, 10.1MB)
효율성  테스트
테스트 1 〉	통과 (31.86ms, 14.2MB)
테스트 2 〉	통과 (27.96ms, 13.1MB)
테스트 3 〉	통과 (36.95ms, 14.7MB)
테스트 4 〉	통과 (34.92ms, 14.1MB)
테스트 5 〉	통과 (31.44ms, 13.9MB)
테스트 6 〉	통과 (39.08ms, 14.8MB)
테스트 7 〉	통과 (35.66ms, 14.4MB)
테스트 8 〉	통과 (29.10ms, 13.7MB)
테스트 9 〉	통과 (31.93ms, 13.9MB)
테스트 10 〉	통과 (33.80ms, 14.5MB)

간만에 빠르게 그리고 한번에 풀린 문제 :)