[Programmers Lv.2 | JS] 땅따먹기

Bori·2023년 8월 21일

Algorithm

목록 보기

21/26

프로그래머스 땅따먹기 문제 링크

첫 번째 풀이

그리디 알고리즘으로 접근하여 다음과 같은 풀이를 작성했습니다.

이 전 인덱스 값이 아닌 현재 열의 숫자 중 최댓값을 찾아 더하기

function solution(land) {
  let answer = 0;
  let prevIndex = 0; // 이 전 인덱스 저장

  // land를 순회하면서, 이 전 인덱스가 아닌 값 중 최댓값을 answer에 저장
  land.forEach((row, index) => {
    // 두 번째 열부터 이 전 인덱스가 아닌 값에서 최댓값을 찾기 위해 
    // 현재 열의 이 전 인덱스 값에 0을 넣어 최댓값에 선택되지 않도록 함
    if(index !== 0) {
        row[prevIndex] = 0;
    }
    
    const maxNumber = Math.max(...row);
    // 현재 열 최댓값의 인덱스를 이 전 인덱스에 저장
    prevIndex = row.indexOf(maxNumber);
    // answer에 최댓값을 더해줌
    answer += maxNumber;        
  })

  return answer;
}

⇒ 테스트 케이스만 통과하고 모두 실패가 뜸

다른 분들의 질문을 통해 반례를 찾아보았습니다.

반례

land가 [[1, 1, 3, 1], [2, 3, 2, 2], [1, 4, 1, 1]]로 주어질 경우,
그리디 알고리즘으로 접근하여 풀면 답은 7이 됩니다.

[
  [1, 1, 3, 1], // ⇒ 3(2) 숫자(인덱스)
  [2, 3, 2, 2], // ⇒ 3(1)
  [1, 4, 1, 1]  // ⇒ 1(0/2/3)
]

answer = 3 + 3 + 1 = 7

하지만, 실제 답은 9입니다.

[
  [1, 1, 3, 1], // ⇒ 3(2)
  [2, 3, 2, 2], // ⇒ 2(0/3)
  [1, 4, 1, 1]  // ⇒ 4(1)
]

answer = 3 + 2 + 4 = 9

무조건 최댓값을 선택한다고 해서 더한 값이 최대가 되는 것은 아닌 거죠.
이럴 경우, 다이나믹 프로그래밍을 적용해볼 수 있습니다.

다이나믹 프로그래밍(Dynamic Programming, 동적 계획법)

다이나믹 프로그래밍은 한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘 입니다.
이를 통해 속도를 향상시킬 수 있는데, 이미 계산한 값을 저장해놓고 동일한 연산을 할 경우 저장된 값을 가져와서 사용하는 메모이제이션을 떠올릴 수 있습니다.

이 문제에서 이 전 열의 최댓값을 현재 열의 각 요소에 모두 더하여 최종 연산된 결과 중 최댓값을 결과로 도출해보려고 합니다.

두 번째 풀이

function solution(land) {
    const COLUMNS_NUMBER = 4

    // land를 순회하면서 같은 열의 숫자를 연속으로 선택하지 않은 각 숫자의 합 배열 생성 
    const sum = land.reduce((acc, cur) => {
        return cur.map((number, index) => {
            // 이 전 행에서 현재 인덱스의 숫자를 제외
            const filter = acc.filter((_, accIndex) => accIndex !== index);
            // 현재 숫자와 이전 행에서 현재 인덱스의 숫자를 제외한 숫자 중 최대값 더하기
            return number + Math.max(...filter);
        })
    // 열의 개수만큼 0으로 초기화 된 배열을 초기값으로 적용
    }, Array.from({ length: COLUMNS_NUMBER }, () => 0));

    // 계산된 합의 최대값을 반환
    return Math.max(...sum);
}

아래의 풀이를 참고해서 위의 풀이를 작성했습니다.
아래의 풀이가 간결하고 좋았지만 하드코딩이라고 생각했고, 이를 개선한 코드를 작성해보고자 위의 코드를 적용해보았습니다.

문제에서 행의 수는 고정이 아니지만 열은 4로 고정되어 있어서 이를 상수로 적용했습니다.
reduce에 0으로 초기화된 배열을 넣어주기 위해 Array.form을 사용했습니다.
각 행에서 이 전 행의 최댓값의 인덱스를 제외한 요소에서 최댓값을 찾기 위해 filter를 사용하여 인덱스가 같은 요소는 제거해주었습니다.

참고한 풀이

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]
    )
  );
}