땅따먹기

내 풀이법

문제해석

• 한 행마다 4개의 열이 주어지며 그 중 숫자 하나를 골라야 한다
• 단 각 행마다 선택하는 열은 일치해서는 안된다. 예를들어 첫번째 행에 첫번째 열을 골랐다면, 두번째 행에 첫번째 열을 골라서는 안된다.
• 선택한 숫자를 모두 더할 때의 최대값을 리턴하시오

 

내가 생각한 풀이법

• [1, 2, 3, 4], [1, 2, 3, 8]이 있다면 첫번째 행과 두번째 행의 가장 큰 값의 열이 일치하여 둘 중 하나를 선택해야한다.
• 이럴 경우 두번째로 큰 값과 제일 큰 값과의 차를 통해 구분할 수 있다.

 

한계점

• 위 방법알 적용하기 위해서는 모든 행들을 스캔하여 근접하는 행들 중 가장 큰 값들의 열이 중복되는 경우를 따로 저장해야한다.
• 만약에 3개의 행의 가장 큰 값의 열이 모두 일치해야한다면 계산 방법이 너무 복잡해진다
• 두번째로 큰 값을 구하는 방법을 따로 구하는 알고리즘을 만들어야 한다.

나의 코드

결국 알고리즘 문제를 풀지 못했다...

다른 사람 풀이법 1

function solution(land) {
  return Math.max(
    ...land.reduce(
      (a, c) => {
        return [
          c[0] + Math.max(a[1], a[2], a[3]),
          c[1] + Math.max(a[0], a[2], a[3]),
          c[2] + Math.max(a[0], a[1], a[3]),
          c[3] + Math.max(a[0], a[1], a[2]),
        ];
      },
      [0, 0, 0, 0]
    )
  );
}

코드특징

1. [0, 0, 0, 0] 부터 시작한다
2. 각 행 내의 열의 값들과 하나씩 더한 경우를 비교하며 그 중 가장 큰 값을 저장한다  
   • 1열이 그 전의 행의 2열 3열 4열씩 더했을 때 가장 큰 값을 저장
   • 2열이 그 전의 행의 1열 3열 4열씩 더했을 때 가장 큰 값을 저장
   • 3열이 그 전의 행의 1열 2열 4열씩 더했을 때 가장 큰 값을 저장
   • 4열이 그 전의 행의 1열 2열 3열씩 더햇을 때 가장 큰 값을 저장
3. 한 행의 모든 열들과 비교를 끝맞췄다면 다음 행의 값들과 비교하며 최대값을 누적한다

• 그 전 행과 더 했을 때 각 열의 최대 누적값들을 저장하여 불필요한 비교과정의 코드를 생략할 수 있다.
• 너무 많은 조건들을 생각해야하는 나의 풀이 접근법과 달리 매우 간결하다.

 

코드성능

• 다른 풀이 코드들 중에 제일 빠르다...

오늘 배운점

• 가능성들이 너무 많을 경우 나의 코드에 조건들을 너무 많이 넣어 복잡하게 풀지 말고 위의 풀이처럼 가능성들을 품을 수 있는 접근법도 있다는 것을 명심하자!