2023년 11월 4일 정수 삼각형

오늘 진짜 더럽게 공부하기가 싫었다.
그래서 알고리즘을 풀었다.

사실 여태 알고리즘 공부를 해봤자 난이도 있는 문제는 몇개 손 대본적이 없었다.
Nqueen이나 Sudoku , Skyscraper 등등.. 42에서 손대본
BackTracking 문제들이었다. 그마저도 시간이 많이 흘렀고

정수 삼각형

3레벨에서 정답률이 가장 높은 문제를 풀어보기로 했다.

정수 삼각형

정수 삼각형

첫 시도

public int solution(int[][] triangle) {
        int answer = 0;
        int target = 0;

        for (int i = 1; i < triangle.length; i++) {
            if (target + 1 < triangle[i].length &&
            triangle[i][target] < triangle[i][target + 1]) {
                answer += triangle[i][target + 1];
                target++;
            }
            else
                answer += triangle[i][target];
            System.out.println((int)triangle[i][target]);
        }
        return answer;
    }

의식의 흐름에 따라 나는 아주 간단하게 코드를 작성하고 제출을 했다.

눈 앞에 보이는 숫자만 보고 제일 크니?
사람으로 따지자면 눈 앞의 이익에만 집중하는 근시안적인 코드다.
출력 결과는 28 로 테스트 케이스의 정답인 30 과는 거리가 멀었다.
즉 큰 숫자만 따라간다고 큰 답이 나오는게 아니다.

모든 결과를 전부 검색해야하지 않나? 완전탐색을 하라고? 설마.
빡대가리 머리에서 나온 첫 의문이었다. 그래도 최소한의 의심은 해봤다.

검색을 해보니 이 문제는 동적 계획법을 이용하는 문제라더라.
dp[][]를 만들어 triangle[][]을 담아 어떻게 한다는데 잠깐 봐서는 모르겠더라.
그래서 그냥 나는 나만의 길을 걷기로 했다.

각 층별 배열을 아래층에 더해 큰 값을 남기는 식으로 김밥 말아가듯 눌러담아보기로.
생각해보니 그럴거면 그냥 거꾸로 아래층에서 밀고 올라가는 식이 낫겠더라
최종 출력 단계에서 가장 아랫층에 남은 숫자들 중, 가장 큰 수를 찾아내면서
굳이 한번 더 로직을 수행하기보다 마지막에 하나만 남기는 방법이
일을 한번 덜 하지 않겠나? (아닐수도 있다. 둘 다 작성해서 굳이 비교해본게 아니라서)

두번째 시도

    public int solution(int[][] triangle) {
        for (int i = triangle.length - 1; i > 0; i--) {
            for (int j = 0; j < triangle[i - 1].length; j++) {
                if (triangle[i][j] + triangle[i - 1][j] >
                triangle[i][j + 1] + triangle[i - 1][j])
                    triangle[i - 1][j] = triangle[i][j] +
                    triangle[i - 1][j];
                else
                    triangle[i - 1][j] = triangle[i][j + 1] +
                    triangle[i - 1][j];
            }
        }
        return triangle[0][0]; 
    }

사실 처음부터 이렇게 한번에 정답이 되진 않았고, 배열을 조회하는 부분에서
실수를 반복하면서 깎아 나가긴 했다.

제출 하니 100점. 다만 가독성이 너무 떨어진다 생각 됐다.

그래서 살짝만 더 손보기로 했다.

세번째 시도

public int solution(int[][] triangle) {
        for (int i = triangle.length - 1; i > 0; i--) {
            for (int j = 0; j < triangle[i - 1].length; j++)
                triangle[i - 1][j] = returnBigger(triangle[i][j] +
                triangle[i - 1][j], triangle[i][j + 1] +
                triangle[i - 1][j]);
            }   
        return triangle[0][0];
    }

    public int returnBigger(int i, int j){
        if (i > j)
            return i;
        else
            return j;
    }

조금 덜 복잡해졌다. 보기에만.
메서드를 하나 더 추가한게 원인인지 실행을 시켜보면 시간이 대략 두배정도 더 걸리더라.
그래봐야 0.02ms에서 0.04ms로, 0.07ms에서 0.14ms 정도로 미세하게 느려진거지만
그래도 엊그제 느낀 바가 있듯, 읽기 편한 코드가 가장 최적의 효율을 내는것은 아니더라.
다시한번 깨닫는 경험이 됐다.


완성한 시점에서 이제야 보이는 부분이 있다.

j < triangle[i - 1].length

이 부분에서 길이를 미리 받아와서 실행시켰으면 아주... 조금 더 빨랐지 않나 ㅋㅋ