코테 연습[자바 코테 준비 13일차] stream 연습

 

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

프로그래머스

 

dp 문제다 . 완탐시 어머무시 하게 가지수가 늘어난다.

 

1차 본인 풀이  정확성 -1 , 효율성 -2 이다.

public int solution1(int[][] triangle) {
    if(triangle.length == 1 )  return triangle[0][0];
    if(triangle.length == 2 )  return Math.max(triangle[0][0] + triangle[1][0] ,triangle[0][0] + triangle[1][1]) ;

    List<Integer> tmp = new ArrayList<>();
    tmp.add(triangle[0][0] + triangle[1][0]);
    tmp.add(triangle[0][0] + triangle[1][1]);
    for(int i = 2 ; i < triangle.length ; i++) {
        List<Integer> sortResult = new ArrayList<>() ;
        for(int j = 0 ; j < triangle[i].length;j++){
            if(j == 0) {
                int givenh = tmp.get(0);
                sortResult.add(triangle[i][0]+givenh);
            } else if (j == triangle[i].length -1) {
                int givenl = tmp.get(tmp.size()-1);
                sortResult.add(triangle[i][i-1]+givenl);
            }else{
                int givenR = tmp.get(j-1);
                int givenL = tmp.get(j);
                sortResult.add(Math.max(givenR,givenL) + triangle[i][j]);

            }
        }
        tmp = sortResult;
    }

    return tmp.stream().max(Comparator.naturalOrder()).orElse(0);
}

 

 

2차 : GPT

public int solution(int[][] triangle) {
    if (triangle.length == 1) {
        return triangle[0][0];
    }

    int[] dp = new int[triangle.length];
    dp[0] = triangle[0][0];

    for (int i = 1; i < triangle.length; i++) {
        dp[i] = dp[i - 1] + triangle[i][i]; // last element in each row

        for (int j = i - 1; j > 0; j--) {
            dp[j] = Math.max(dp[j - 1], dp[j]) + triangle[i][j];
        }

        dp[0] += triangle[i][0]; // first element in each row

    }

    int maxSum = 0;
    for (int num : dp) {
        maxSum = Math.max(maxSum, num);
    }

    return maxSum;
}

 

다른 사람의 풀이 중

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

    return Arrays.stream(triangle[triangle.length-1]).max().getAsInt();
}