[Java] 정수 삼각형

프로그래머스 문제

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

풀이 후기

1. 날로 먹기

나는 코테 문제를 날로 먹는 걸 좋아한다. 넥슨 코테 중 1문제도 대충 배열하고 flag로 풀었는데, 테스트 케이스 전부 다 맞으니 기분이 좋더라. 이번 문제는 내용만 대충 확인했는데 c#이 없어서 안 풀고 자려고 했다. 그런데 양치질하다가 10분 정도만 하면 될 것 같아서 그냥 풀기로 했음.

2. 노드 싫어

피라미드 모양이 트리 쓰라고 만든 거 같은데 만들기도 귀찮고 그냥 (x+1, y), (x+1, y+1)하면 풀만 할 것 같았다. 재귀로 하는 방법도 있었는데 머리아파서 금방 포기했다. 옛날부터 재귀랑 별로 친하지 않음. 탐색하는 방법은 위에서 아래로 내리기, 아래에서 위로 올리기 2가지 방법이 생각났는데 위에서 아래로 내리면 나중에 Max 한 번 돌려야 해서 아래서 올리기로 결정.

3. 잠시 고민

원래 자기 숫자를 위에 올려보내는 걸로 구상했는데, 써 놓고 보니 그냥 숫자 다 더하는 코드라서 생각을 좀 더 했다. 그래서 바꾼 방법은 자기 자식 중 더 큰 놈을 가져와서 올라가는 구조로 했다. 이러면 [0][0] 에서 가장 큰 값이 최종 우승하는 느낌으로.

효율성 테스트 같은거 있는지 몰랐는데 한번에 통과해서 다행.

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        int len = triangle.length;
        
        for(int x = len - 2; x >= 0; x--){
            for(int y = 0; y <= x; y++){
                int a = triangle[x + 1][y];
                int b = triangle[x + 1][y + 1];
                triangle[x][y] += Math.max(a, b);
            }
        }
        
        return triangle[0][0];
    }
}

오랫만에 자바. 근데 c#이나 자바나 뭐...