[프로그래머스/Level2] 땅따먹기 (Java)

문제

https://programmers.co.kr/learn/courses/30/lessons/12913?language=java 

코딩테스트 연습 - 땅따먹기

---

 

풀이

제한사항

• 땅따먹기 땅(land)은 N행 4열이다. (2차원 배열)
  • 행의 개수 N : 100,000 이하의 자연수
  • 열의 개수는 4개로 고정
• 모든 칸에는 점수가 쓰여있다. (칸 개수 = N * 4)
  • 점수 : 100 이하의 자연수
• 1행부터 N행까지 한 칸만 밟으면서 내려온다.
• 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없다.
• 마지막 N행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 구하라.

 

접근방식

행에서 밟은 모든 점수들을 더한 최종 점수가 최대값인 경우로 내려와야하기 때문에, 단순히 매 행의 최대값을 밟는 식으로 내려와서는 안된다. 예를 들어 1행의 최대값이 4열의 10, 2행의 최대값이 4열의 100일 경우, 1행에서 4열의 10을 밟아버리면 다음 행에서 4열 값을 연속으로 밟을 수 없게된다. 이러면 10보다 훨씬 큰 100이라는 점수를 놓치게 되는 것이다. 1행에서 최대값이 아닌 아무 수나 밟고, 2행에서 4열의 100을 밟는 편이 최종 점수가 훨 커지는 경우이다.

행의 개수가 N개 일 때, 마지막 행까지 모두 내려왔을 때 얻을 수 있는 점수의 최대값은 'N-1 행까지 내려왔을 때 얻을 수 있는 점수의 최대값 + N행에서 가장 큰 점수' 이다. 그런데 위에서 설명한 바와 같은 열을 연속으로 밟을 수 없기 때문에

• N-1 행까지 내려왔을 때 최대값을 얻기 위해서 밟아야 하는 N-1행의 열
• N행에서 가장 큰 점수의 열

두 열이 같은지 여부를 체크해야 한다. 만약 두 열이 다르다면 그대로 'N-1 행까지 내려왔을 때 얻을 수 있는 점수의 최대값 + N행에서 가장 큰 점수' 가 최대값이 되게된다. 그러나, 두 열이 같으면 더 큰 점수를 가진 행의 열은 그대로 밟되, 작은 점수를 가진 행은 다른 열을 밟아야 한다.

이런식으로 각 행까지 내려왔을 때 얻을 수 있는 최대값을 배열에 메모하는 DP(Dynamic Programming)방식으로 풀어보도록 하자. 연속으로 같은 열을 밟지 않도록 각 행까지 내려왔을 때 최대값을 얻기위해 마지막으로 밟은 열의 인덱스도 기억해둬야 한다.

 

코드

import java.util.Arrays;

class Solution {
    int solution(int[][] land) {
        int answer = 0;
        int[] score = new int[land.length + 2];      // 현재 행까지 내려왔을 때 얻을 수 있는 최대값
        int[] column = new int[land.length + 2];     // 마지막으로 밟은 열 index
        Arrays.fill(column, -1);

        // 행 내려가기
        for (int i = 0; i < land.length; i++) {
            for (int j = 0; j < 4; j++) {
                if (land[i][j] > score[i + 1] && column[i] != j) {	// 이전에 밟은 열이 아닌 최대값
                    score[i + 1] = land[i][j];
                    column[i + 1] = j;
                    // System.out.println("열 : " + j + ", 점수 : " + score[i + 1]);
                }
            }
            System.out.println();
        }

        for (int i : score) {
            answer += i;
        }

        return answer;
    }
}

위 코드는 이전 행에서 밟은 열이 아니면서 가장 점수가 큰 열을 차례로 밟은 뒤, 마지막에 최종 점수 합을 반환하는 방식이다. 코드 실행 시에는 테스트에 통과하지만 실제 실행결과는 전부 실패가 뜬다.

 

이전 행에서 밟은 행은 밟지 않는 방식이 아니라, 이전행에서 밟은 열 점수와 이번 행의 최대 열 점수를 비교해 그 값에 따라 이전 행 / 현재 행 중 하나의 열을 변경하고, int[] dp 배열을 활용한 다이나믹 프로그래밍(DP) 방식으로 코드를 개선해보자.

변경사항

• 매개변수로 받은 land[][] 2차원 배열을 그대로 메모용 dp배열로 사용
• land[][] 배열의 각 칸에 'i가 마지막 행이라고 했을 때, j열을 선택했을 경우 가능한 최대값' 을 저장한다.
• 예를들어 land[1][0] 칸 값은 (0번째 행에서 0열을 제외한 최대 점수 + land[1][0] 점수) 이다.
  1행에서 0열을 선택하기 위해서는 0행에서는 무조건 0열을 제외한 다른 열을 선택해야 하기 때문이다.
• 1차원 배열에서 특정 인덱스를 제외했을 때 최대값을 반환하는 메서드를 따로 빼두려 했으나, 이번 문제는 열을 의미하는 1차원 배열 크기가 4로 고정되어 있기 때문에 Math.max() 메서드만을 사용해 간단히 작성하기로 했다.

 

import java.util.Arrays;

class Solution {
    int solution(int[][] land) {
        int answer = 0;
        // 행 개수대로 반복
        for (int i = 1; i < land.length; i++) {
            // 0번째~3번째 열까지 (해당 칸의 점수 + 이전 행에서 특정 열을 제외한 최대값) 갱신
            land[i][0] += Math.max(land[i - 1][1], Math.max(land[i - 1][2], land[i - 1][3]));
            land[i][1] += Math.max(land[i - 1][0], Math.max(land[i - 1][2], land[i - 1][3]));
            land[i][2] += Math.max(land[i - 1][0], Math.max(land[i - 1][1], land[i - 1][3]));
            land[i][3] += Math.max(land[i - 1][0], Math.max(land[i - 1][1], land[i - 1][2]));
        }
        
        // 마지막 행에서 최대값
        for (int i : land[land.length - 1]) {
            answer = Math.max(answer, i);
        }

        return answer;
    }
}

 

 

• land[][] 2차원 배열에서 열을 의미하는 1차원배열의 크기가 4로 고정되어 있지 않았다면, 아래와 같이 특정 인덱스를 제외하고 1차원 배열에서 최대값을 반환하는 코드를 작성해서 Math.max() 부분을 대체해줘야 한다.

// 특정 인덱스를 제외하고 1차원 배열에서 최대값 반환하는 메서드
int maxNotIndex(int idx, int[] arr) {
    int max = arr[0];

    for (int i = 1; i < arr.length; i++) {
        if(i == idx) continue;
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}