[프로그래머스] 땅따먹기 (Lv 2) - javascript

📝 문제

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(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 이하의 자연수

📌 풀이

프로그래머스 문제풀이 영상을 토대로 정리한 내용이다.

a까지 이르는 경로는 다양하겠지만, 일단 a에 이르고 나서 탐색되는 아래 부분은 항상 같다.

이는 a까지 어떤 경로를 선택하던지 얻을 수 있는 최대값을 항상 같다는 것이다.

그러므로 그 값을 저장해두면 다음에 다른 경로로 a에 오더라도 사용할 수 있어 효율적이다.

a, b, c, d 에서 출발했을 때 얻을 수 있는 최대값을 모두 저장해놨을 때

K지점에서 출발해 얻을 수 있는 최고 점수는 아래와 같다

• K지점의 값 = land[i][0]
• K에서 출발해 얻을 수 있는 최대값 = dp[i][0]

∴ dp[i][0]
= dp[i][0] = max(dp[i+1][1], dp[i+1][2], dp[i+1][3]) + land[i][0]
=> b, c, d 각각 위치에서 출발해서 얻을 수 있는 최대값 중에서 최대값 + K 위치의 값

출발 위치를 달리 했을 때의 최대값은 아래와 같다.

경로를 거꾸로 해서 밑에서 위로 올라가는 경로로 계산해도 값은 같다.

📌 구현

1️⃣ 1차 풀이

function solution(land) {

    for(let i = land.length - 2; i >= 0; i --) { 
        land[i][0] = Math.max(land[i+1][1], land[i+1][2], land[i+1][3]) + land[i][0];
        land[i][1] = Math.max(land[i+1][0], land[i+1][2], land[i+1][3]) + land[i][1];
        land[i][2] = Math.max(land[i+1][0], land[i+1][1], land[i+1][3]) + land[i][2];
        land[i][3] = Math.max(land[i+1][0], land[i+1][1], land[i+1][2]) + land[i][3];
    }
    return Math.max(...land[0]);
}

위 풀이는 행을 아래부터 위로 순회하며 (밑에서 두 번째 행이 시작) 각 값을 경로 이동의 최대값으로 바꿔준다.
따로 저장하는 것이 아니라 각 위치의 값을 바꿔주는 것이다. 그것이 훨씬 효율적이고 간단하다.

여기서 알아야 할 것은 위 과정을 통해 각 위치에는 그 위치로 오면서 더해진 최대값이 저장되어 있다.
그러므로 Math.max()로 최대값을 선택하는 것이 단순히 원래 land의 값의 최대값이 아님을 명심해야 한다.
위와 같은 과정을 거치지 않고 무조건 다음 행의 최대값을 선택해서 이동한 경로는 정답이 아니다.

• 정확도 테스트 결과

  

• 효율성 테스트 결과

  

2️⃣ 2차 풀이

function solution(land) {

    return Math.max(...land.reduce((ac, v) => 
        [v[0] + Math.max(ac[1], ac[2], ac[3]),
         v[1] + Math.max(ac[0], ac[2], ac[3]),
         v[2] + Math.max(ac[0], ac[1], ac[3]),
         v[3] + Math.max(ac[0], ac[1], ac[2])]));
}

위 코드를 reduce로 구현한 풀이다.

위에서 아래로 최대값을 구해서 각 위치에 저장한다.

맨 처음은 1행의 값이 그대로 저장되고, 그 다음 행부터 전에 거쳐온 열을 제외한 값 중 최대값을 더한다.

순회마다 최대값이 점차 더해져서 마지막에는 각 경로의 최대값만 남게 된다.

• 정확도 테스트 결과

  

• 효율성 테스트 결과

  

3️⃣ 3차 풀이

function solution(land) {

    for(let i = land.length-2; i >= 0; i--) {
        land[i] = land[i].map((v,idx) => v = v + Math.max(...land[i+1].filter((e,i) => i !== idx)));
    }

    return Math.max(...land[0]);
}

오랜만에 다시 풀어보니 나에게서 이런 답이 나왔다ㅋㅋㅋ

메서드를 많이 이용해서 속도와 효율성은 다소 느리다.

• 정확도 테스트 결과

---

참고

hongjw1938.tistory
https://velog.io/@sso/
https://programmers.co.kr/learn/courses/30/