프로그래머스_땅따먹기(JAVA)

https://programmers.co.kr/learn/courses/30/lessons/12913

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

문제 설명

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

예를 들면,

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |

로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

제한사항

• 행의 개수 N : 100,000 이하의 자연수
• 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.
• 점수 : 100 이하의 자연수

입출력 예

land	answer
[[1,2,3,5],[5,6,7,8],[4,3,2,1]]	16

 

[문제 분석]

모든 경우의 수를 탐색해가며 계산하게 된다면 수행 시간이 너무 오래 걸릴 것 같다고 여겨서 어떻게 문제를 해결해야 할까 생각해보았다. Greedy로 첫번째 행부터 마지막 행까지 전에 방문한 열을 제외한 열에서 최댓값을 찾아 더해나가는 방식으로 문제를 해결한다면 정확한 답이 나오지 않을 것이므로 고민이 많이 되었다.

그래서 land 배열의 값을 직접 바꿔가며 문제를 해결하기로 하였다.

해당 행에서 각 열을 선택했을 때 이전 행의 어떤 값과 더했을 때 최대가 될지, 그리고 그 값을 해당 행에 저장하는 방식으로 문제를 해결하였다.

 

예를 들어,

[1, 2, 3, 5]

[5, 6, 7, 8]

이 두 행을 보자.

 

우선 2행의 1열(5)을 선택했을 때 그 값이 최대가 되는 것은 1행의 1열을 제외한 열 중에서 최댓값인 4열의 5를 선택했을 때 최대가 된다. 그러므로 2행의 1열은 10(=5+5)으로 값을 변경하여준다.

같은 방식으로 2행의 2열(6)을 선택했을 때 그 값이 최대가 되는 경우는 1행의 2열을 제외한 열 중 최댓값인 4열의 5를 선택했을 때이므로 2행의 2열은 11(6+5)로 값을 변경하여준다.

 

이러한 방식으로 2행의 4열까지 모두 보았을 때 저장된 결과는

[1, 2, 3, 5]

[10, 11, 12, 11]

다음과 같이 저장될 것이다.

 

이제 3행인 [4, 3, 2, 1]은 방금 값을 변경해준 2행 [10, 11, 12, 11]을 이용하여 위와 같은 방식으로 진행한다.

그렇다면 3행에는 [16, 15, 14, 13]이 될 것이다.

 

모든 행에 대해 다음 작업이 완료되었다면, 최댓값을 찾아주어야 한다.

land의 마지막 행에 대해 모든 열을 반복문으로 검사하여 최댓값을 찾은 후 그 값을 반환한다.

 

[코드]

class Solution {
    int solution(int[][] land) {
       
        int max=0;
      
        int[] temp = new int[4];
        int[] temp2 = new int[4];
        int idx=0;
      
        
        for(int i=1;i<land.length;i++){
            for(int j=0;j<4;j++){
                max=0;
                for(int k=0;k<4;k++){
                    if(k==j)
                        continue;
                    else{
                        if(max<land[i-1][k]){
                            max=land[i-1][k];
                        }
                    }
                }
                land[i][j] += max;
            }
        }
        
        
        max=0;
        for(int i=0;i<4;i++){
            if(max<land[land.length-1][i])
                max=land[land.length-1][i];
        }
        
        return max;
    }
}