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

문제

 

문제풀이

public int solution(int[][] land) {     //땅따먹기 문제
    for(int i=1; i<land.length; i++){   //최대값을 가려내는 반복문 작성
        land[i][0] += Math.max(Math.max(land[i-1][1], land[i-1][2]), land[i-1][3]);
        land[i][1] += Math.max(Math.max(land[i-1][0], land[i-1][2]), land[i-1][3]);
        land[i][2] += Math.max(Math.max(land[i-1][1], land[i-1][0]), land[i-1][3]);
        land[i][3] += Math.max(Math.max(land[i-1][1], land[i-1][2]), land[i-1][0]);
    }

    int[] answer = land[land.length-1];
    Arrays.sort(answer);

    return answer[answer.length-1];
}

사실 이 문제를 for문을 정말 많이 써서 풀었는데 효율성도 100% 통과 못하고 코드 실행 시간도 느려서 몇가지 통과를 못해서 찾아봤는데 정말 골때리는 풀이가 있어서 이렇게 가져와봤다.

 

우선, 나는 각 줄에서 제일 큰 값을 찾고 그게 그 앞줄이랑 index값이 겹치면 그 다음으로 큰 값을 찾는 식으로 문제를 풀었는데, 이 풀이는 그게 아니고 아예 다른 사고방식으로 접근을 했다.

 

위의 풀이 코드를 해석을 해보자면, for문에서

land[i][0] += Math.max(Math.max(land[i-1][1], land[i-1][2]), land[i-1][3]);

이것이 의미하는 바는

1. 그 다음 줄[i]의 첫번째 index값에는 그 전 줄[i-1]의 첫번째 index값이 못 들어간다.

2. 그러므로 그 전 줄의 첫번째 index값인 0을 제외한 나머지 값 중에 제일 큰 값을 그 다음 줄의 첫번째 index값에 더한다.

3. 이 과정을 첫번째 index뿐만 아니라 마지막 index([3])까지 다 해준다.

 

그리고 이것을 for문 코드에 의해 land[0][0] ~ land[land.length-1][3]까지 쭉 값을 다 더해준다.

int[] answer = land[land.length-1];

이 코드로 answer에 land의 제일 마지막 줄의 배열을 다 집어넣고

오름차순으로 정렬을 한뒤,

배열 answer에서 제일 뒤에 있는 값(제일 큰 값)을 return한다.

 

 

이게 답을 알고보면 정말 간단하고 쉬운 원리인데 문제를 풀 땐, 왜 이 생각이 안나던지...

알고리즘을 풀면서 또 하나의 새로운 방법을 배워간다.