[프로그래머스] 땅따먹기 - 자바스크립트

[ 문제 설명 ]

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

---

[ 아이디어 ]

1. 완전 탐색 기법으로 푼다
2. 색다른 로직을 활용해 푼다.

[ 코드 ]

1. 완전 탐색 기법으로 푼다.

아이디어의 경우 갈 수 있는 모든 경로를 사전에 생성하고 하나씩 비교하면서 가장 큰 값을 찾는 로직입니다. 

permutation을 이용해 모든 경로를 생성하고

availPath 함수를 통해 갈 수 있는 경로만 최대값을 계산합니다.

테스트는 통과했지만 실행결과 시간초과가 뜨고 말았습니다.

function solution(land) {
  let answer = 0;
  let allPath = permutation([1, 2, 3, 4], land.length);
  allPath.forEach((item) => {
    let pathPrice = land.reduce((acc, cur, i) => {
      return acc + cur[item[i] - 1];
    }, 0);
    if (pathPrice > answer) answer = pathPrice;
  });

  return answer;
}

function permutation(arr, selectNum) {
  const result = [];
  if (selectNum === 1) return arr.map((v) => [v]);

  arr.forEach((v, idx, arr) => {
    const fixed = v;
    const restArr = arr;
    const permutationArr = permutation(restArr, selectNum - 1);
    const combineFix = permutationArr.map((v) => [fixed, ...v]);
    combineFix.forEach((item) => {
      if (availPath(item)) result.push(item);
    });
  });
  return result;
}

function availPath(arrPath) {
  for (let i = 0; i < arrPath.length - 1; i++) {
    if (arrPath[i] === arrPath[i + 1]) return false;
  }
  return true;
}

아이디어1. 시간초과

 

2. 색다른 로직을 활용해 푼다.

이번에는 색다른 로직을 생각해봅시다. 한줄의 땅에서 다음땅으로 갈 수 있는 최대값을 하위값에 그대로 더해주는 로직입니다.

| 1 | 2 | 3 | 5 |   => | 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |   => | 10 | 11 | 12 | 11 |     

// 마지막 11은 윗줄에서 가능한 큰 수 3과 본인 8을 합한 것 ( 5는 같은 자리라 안됨)

| 4 | 3 | 2 | 1 |   => | 16 | 15 | 13 | 13 |       

// 16은 윗줄에서 가능한 큰 수 12와 본인 4를 합한 것

이런 방식으로 아래로 계속 더해나가는 로직입니다.

function solution(land) {
  let answer = 0;
  const landLength = land.length;
  for (let i = 0; i < landLength - 1; i++) {
    land[i + 1][0] += Math.max(land[i][1], land[i][2], land[i][3]);
    land[i + 1][1] += Math.max(land[i][0], land[i][2], land[i][3]);
    land[i + 1][2] += Math.max(land[i][0], land[i][1], land[i][3]);
    land[i + 1][3] += Math.max(land[i][0], land[i][1], land[i][2]);
  }
  answer = Math.max(
    land[landLength - 1][0],
    land[landLength - 1][1],
    land[landLength - 1][2],
    land[landLength - 1][3]
  );
  return answer;
}

코드에 반복이 많아 보이긴 하지만 가장 직관적인 느낌으로다가 구현해봤습니다.

---