[ Programmers ] lv2_땅따먹기(JS)

프로그래머스

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

입출력
예 ) landanswer[[1,2,3,5],[5,6,7,8],[4,3,2,1]] 16

 

풀이

처음엔 Math.max를 이용하여 최대값을 찾고 indexOf 로 최대값 위치를 찾아서 포문을 이용해서 
land 배열안의 요소의 인덱스 1부터 시작해서 로직은 밑에 있는 로직과 같은 방식으로 했었는데 
테스트키는 맞는데 채점에서 전부 다 틀렸다고 나와서 많이 헷갈렸는데
알고리즘 스터디를 진행할 때 이런 비슷한 문제에 dp를 사용했던 분이 생각나서 dp로 갈아탔다.
아마 효율성 때문인 것도 있고 문제 자체가 dp 형식으로 풀어야 풀리는 문제 인 것 같다.

dp로 풀게되면 이전 행에서의 최적값과 현재 열에서의 값만을 이용하여
최대값을 계산할 수 있기 때문에 시간 복잡도가 효율적으로 개선된다.
dp 배열을 이용하여 다음과 같은 방법으로 문제를 해결했다.

dp 배열의 첫 번째 행은 그대로 두고, 두 번째 행부터 순회한다.
각 행마다, 이전 행에서 자신을 제외한 나머지 열 중에서 가장 큰 값을 구한다.
현재 행의 각 열에 대해서, 이전 행에서 구한 가장 큰 값과 더한다.
dp 배열의 마지막 행에서 가장 큰 값을 구한다.

getMaxValue() 함수에서하는 일
각 행에서 가장 큰 값을 구함
주어진 행에서 인덱스 exceptIndex를 제외한 나머지 열 중에서 가장 큰 값을 반환

 

code

// dp : 문제를 작은 부분 문제로 나누어 푸는 방법
function solution(land) {
  // land 배열 복사해서 dp 배열 저장
  const dp = [...land];
  
  // 두번째 행 부터 마지막 행까지 getMaxValue 함수에 보내서 받은 max 값을 받아서 누적 계산
  for (let i = 1; i < dp.length; i++) {
    for (let j = 0; j < dp[i].length; j++) {
      // getMaxValue -> 이전 행에서 선택한 열을 제외한 나머지 열 중에서 최대값을 찾아와서 현재 요소에 더해줌
      dp[i][j] += getMaxValue(dp[i - 1], j);
    }
  }
  // dp 배열의 마지막 행에서 최대값을 찾아 반환
  return Math.max(...dp[dp.length - 1]);
}
// 현재 칸을 제외한 이전 행에서의 최대값 구하는 함수
function getMaxValue(row, exceptIndex) {
  let max = 0;
  for (let i = 0; i < row.length; i++) {
    // 현재 칸이 아니면서, i번째 칸의 값이 현재까지 찾은 최대 값 보다 크다면 최대 값을 갱신
    if (i !== exceptIndex && row[i] > max) {
      max = row[i];
    }
  }
  // 최대 값 리턴
  return max;
}