[프로그래머스] LEVEL2 땅따먹기 JAVA

땅따먹기

문제링크

풀이

dp
1. land에 이전 값의 같은 열을 제외하고 가장 큰 값을 더해주는 과정을 반복하며 표시한다.
2. 최종 마지막 land 행의 값중 최댓값을 선택하면 된다.

+) 다른 사람의 풀이는 열이 4개라는 점을 활용해 각 열마다 이전 행의 같은 열의 제외하고 max 함수를 활용해 바로 구하였다.
나의 경우, list로 변환해 정렬하고 다시 인덱스가 같은지를 확인하는 과정을 거쳐서 조금 과정이 복잡해보인는데
문제에 주어진 내용을 활용해 풀이하니 코드가 짧고 간결해보였다.

코드

import java.util.*;
class Solution {
    public class Land {
        int idx;
        int score;
        public Land(int idx, int score) {
            this.idx = idx;
            this.score = score;
        }
        
        @Override 
        public String toString() {
            return score + " " + idx;
        }
    }
    public int N, M;
    int solution(int[][] land) {        
        N = land.length;
        M = land[0].length;
        int answer = 0;
        
        for (int i = 1; i < N; i++) {
            List<Land> list = new ArrayList<>();
            for (int j = 0; j < M; j++) {
                list.add(new Land(j, land[i - 1][j]));
            }
            
            Collections.sort(list, new Comparator<Land>() {
                @Override
                public int compare(Land o1, Land o2) {
                    return o2.score - o1.score;
                }
            });

            Land first = list.get(0);
            Land second = list.get(1);
            
            for (int j = 0; j < M; j++) {
                if (first.idx == j) {
                    land[i][j] += second.score;
                    continue;
                }
                land[i][j] += first.score;
            }
        }
        
        for (int i = 0; i < M; i++) {
            answer = Math.max(land[N - 1][i], answer);
        }
        return answer;
    }
}