이번에 풀어본 문제는
프로그래머스 땅따먹기 입니다.

📕 문제 링크

❗️코드

import java.util.*;

class LandPoint {
    int idx, point;

    public LandPoint(int idx, int point) {
        this.idx = idx;
        this.point = point;
    }
}
class Solution {
    int solution(int[][] land) {
        int answer = 0;
        int n = land.length;

        if (n < 2) {

            for (int i = 0; i < 4; i++) answer = Math.max(answer, land[0][i]);
            return answer;
        }

        List<LandPoint> list = new ArrayList<>();

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 4; j++) {
                list.add(new LandPoint(j, land[i - 1][j]));
            }

            list.sort(new Comparator<LandPoint>() {
                @Override
                public int compare(LandPoint o1, LandPoint o2) {
                    return o2.point - o1.point;
                }
            });

            for (int j = 0; j < 4; j++) {
                int point = list.get(0).idx != j ? list.get(0).point : list.get(1).point;
                land[i][j] += point;
            }
            list.clear();
        }

        for (int i = 0; i < 4; i++) answer = Math.max(answer, land[n - 1][i]);

        return answer;
    }
}

📝 풀이

주어진 2차원 배열에서 동일한 열을 제외한 다른 열로 하행 이동하여 누적한 가장 큰 값을 반환하는 문제입니다.
행에 있는 모든 값을 탐색하여 값이 큰 순서대로 정렬시킨 후, 다음 행에서 덧셈을 진행합니다.
정렬된 리스트의 가장 첫 번째 인덱스를 꺼냈을 때, 자신과 인덱스가 다르다면 (다른 열이라면) 그대로 더하고, 같은 인덱스라면 다음 값을 더해주기만 하면 됩니다.
모든 반복을 마치고 마지막 행에서 가장 큰 값을 반환해주면 해결할 수 있습니다.

사실 무조건 효율성에서 걸릴 것 같았는데, 이정도로도 통과가 되는 문제네요