프로그래머스 정수 삼각형(lvl3)풀어보기

문제링크

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

프로그래머스

---

문제 핵심

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

---

알고리즘

-두줄씩 문제조건대로 더함

해당 행에 열끼리 더한값을 묶음

해당 좌표의 최고합만 구함

그리고 최고가를 매번 갱신함

---

코드

 static int solution(int[][] triangle) {

        int answer = 0;

        int index = 0;

        int[] maxs = new int[triangle[triangle.length - 1].length];

        maxs[0] = triangle[0][0];

        while (index < triangle.length - 1) {

            int[] tempMaxs = new int[triangle[index + 1].length];

            for (int i = 0; i < triangle[index].length; i++) {

                for (int ii = i; ii < Math.min(i + 2, triangle[index + 1].length); ii++) {

                    System.out.println("연산예정: " + maxs[i] + " + " + triangle[index + 1][ii]);

                    int nmax = maxs[i] + triangle[index + 1][ii];

                    tempMaxs[ii] = Math.max(tempMaxs[ii], nmax);

                }

            }

            System.out.println("최고값후보현황: " + Arrays.toString(tempMaxs));

            for (int i = 0; i < tempMaxs.length; i++) {

                if (maxs[i] < tempMaxs[i]) {

                    maxs[i] = tempMaxs[i];

                }

                if (answer < tempMaxs[i]) {

                    answer = tempMaxs[i];

                }

            }

            System.out.println("최고값현황: " + Arrays.toString(maxs));

            index += 1;

        }

        System.out.println(answer);

        return answer;

    }

 

---

결과

---

gpt피드백

알고리즘

알고리즘부터 보면 지금 방향은 적절해.

시간복잡도는 삼각형의 전체 원소 수만큼 처리하니까 O(n²), 추가 공간은 maxs, tempMaxs 때문에 **O(n)**이야. 이 문제에서는 충분히 좋은 수준이야

코드에서 가장 크게 개선할 부분

1. Math.min()은 필요 없어.

삼각형 구조상 i에서 다음 행의 i, i+1은 무조건 존재해.

for (int ii = i; ii < i + 2; ii++) {

로 충분해.

1. maxs에 다시 Math.max() 할 필요가 없어.

지금 tempMaxs 자체가 해당 위치까지 도달하는 최댓값을 이미 계산했잖아.

1. answer를 매 행마다 구할 필요도 없어.

우리가 원하는 건 마지막 층에 도착했을 때의 최댓값이니까 중간마다:

if (answer < tempMaxs[i]) {
    answer = tempMaxs[i];
}

 

 

 

---

후기

-조금전에 푼문제랑 아주 비슷해서

쉽게 풀었다 다만 map을 쓰니 효율성 통과가안돼어서

이전 문제에서 gpt가 줬던 피드백을 반영해 제출했더니

성공했다