프로그래머스_Level.2 땅따먹기

1.문제설명

문제: 땅따먹기

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 하면 됩니다.

 

2.제한 조건

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

3.입출력 예

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

 

📌나의 풀이

첫번쨰로 풀었던 방법은 for문을 사용하는 것이었다. 하지만 테스트 케이스에서는 오류가 나지 않았지만 제출을 하니 오류가 났다. 질문들을 찾아보니 내 코드에 문제점을 발견했다. 

 

아래 코드는 첫번째 작성 코드로 오류가 나는 코드이다. 

 

잘못된 풀이 방식

 

첫 번쨰 행부터 탐생르 하며 가장 큰 수를 고르고 

그 다음 행에서 같은 열에 있는 수를 제외한 최대값을 고르는 과정을 반복한다.

 

function solution(land){
    
    var answer = [];
    
    var sum = 0;
    var idx = 0;
    
    for(var l = 0; l<4; l++){
        var ex = [land[0][l]]
        idx = l;
        for(var i=1; i<land.length; i++){
            var temp;
            var max = -1;
            for(var j=0; j<land[i].length; j++){
                if(idx===j)continue;
                if(max<land[i][j]){
                    max = land[i][j];
                    temp = j;
                }
            }
            ex.push(max);
            idx = temp;
        }
        answer.push(ex.reduce((acc,cur)=>acc+cur));
    }
  
    return Math.max(...answer);
}

일단 삼중 for문을 사용하는 것 부터 시간적 효율성이 떨어진다.  그리고 가장 큰 문제점으로 열에서 같은 점수가 있을 때 결과가 똑바로 나오지 않는다. 

예를 들면  [[4, 3, 2, 1], [2, 2, 2, 1], [6, 6, 6, 4], [8, 7, 6, 5]] 상황일 때이다.

4를 고르고 2행에서2열의 2를 선택하고 3행에서 1열의 6을 선택하고 4행에서 2열의 7을 선택해서 가장 큰 값을 찾지못한다.  

아래의 값까지 같이 처리를 해주면 코드가 더욱더 길어지면 시간이 더 오래 걸릴것같았다. 

혼자서 코드를 고민해보다가 방법이 나오지 않아서 다른 사람들의 코드를 참고했다.

 

 

 

n번째 행에 값들에 n-1번쨰 행들의 값을 더해줘 쌓아주는 방식으로 푼 사람의 코들를 발견했다. 파이썬 코드였지만 코드가 엄청 간결하고 내가 첫번째로 풀었던 방법보다 훨씬더 효율적이었다. 

function solution(land){
    
    var answer = 0;
    
    var n = land.length; //행의 개수 
    
    for(var i=0; i<n-1; i++){
        
        land[i+1][0] += Math.max(land[i][1],land[i][2],land[i][3]);
        //i번쨰 행에 0번쨰 열에는 i번째 행에 1,2,3 열 중 최댓값을 더해준다.  
        land[i+1][1] += Math.max(land[i][0],land[i][2],land[i][3]);
        land[i+1][2] += Math.max(land[i][1],land[i][0],land[i][3]);
        land[i+1][3] += Math.max(land[i][1],land[i][2],land[i][0]);
    }
    //console.log(land);
    answer = Math.max(...land[n-1]);
    return answer;
}

이 알고리즘을 보고 이렇게 간단하게 생각할 수 있구나 라는 생각이 들었다.

다른 문제를 풀 때도 위에서 부터 순차적으로 값을 찾는 것이 아니라 n번째 행에 값들에 n-1번쨰 행들의 값을 더해줘 쌓아주는 것처럼 다양한 방식을 생각해 보아야겠다. 

 

 

💡배운점

• 처음부터 여러 가지 예시들을 고려해서 작성했다면 실수를 줄일 수 있었을 것이다.
• 거꾸로 생각하는 법에 대해서 배웠다.

 

✔참고 자료

ssungkang.tistory.com/entry/%EB%95%85%EB%94%B0%EB%A8%B9%EA%B8%B0%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4level2