[프로그래머스] level.2 땅따먹기

 

프로그래머스

 

---

나의 풀이 

 

문제를 읽어보면 핵심은 일직선으로 내려갈 수 없다.   

 

고려해야할 사항

 

1. 행에 같은 점수가 있는 경우

한 행에 같은 점수가 있는 경우도 고려하셔야 합니다.
[[4, 3, 2, 1], [2, 2, 2, 1], [6, 6, 6, 4], [8, 7, 6, 5]] => 20

2. 무조건 최댓값을 고르면 안된다.

[[1, 2, 3, 4], [2, 3, 4, 100]] => 103

간단한 예시로 첫 번째 행에서 최댓값인 4를 고르면 두 번째 행에서 100을 고를 수 없기 때문에 이 부분도 고려해야 합니다.

연속으로 같은 열 불가능

 

 

 

미리 이를 고려하고 테스트케이스에 넣어주면 훨씬 좋습니다.

 

전체적인 계획은  제일큰 것과 그 다음 큰것을 선택했을 때의 모든 경우의 수를 따진 다음 그것들의 최대값을 뽑아내자는 생각이었습니다.

 

예외)

1 )이전 행과 같은 행의 숫자는 제외 

2 )제일 낮은 숫자는 제외 

 

코드 흐름 

1. 제일 큰 숫자와 그 다음 큰 숫자를 선택한다. 

2. 그 숫자의 행과 같지않은 제일 큰 숫자와 그 다음 큰 숫자를 선택한다.  

3. 1,2를 반복한다.  

 

아래처럼 풀면 테스트케이스는 통과하지만 시간이 너무 오래걸려서 런타임 오류가 발생한다.  

 

틀린 풀이

function solution(land) {
    const result = []
    
    const typeDict ={
        0: "first",
        1: "second",
        2: "third",
        3: "fourth"
    }
    const maxNumber = Math.max(...land[0])
    const maxNumberIndex = land[0].indexOf(maxNumber)
    const tmp = [...land[0]]
    tmp.splice(maxNumberIndex,1)
    const nextMaxNumber = Math.max(...tmp)
    const nextMaxNumberIndex = land[0].indexOf(nextMaxNumber)
    callback(0, maxNumberIndex)
    callback(0, nextMaxNumberIndex)
    
    function callback( index, type, sum = 0){
        if(land.length  === index){
            result.push(sum)
            return
        }
        const [first, second, third, fourth] = land[index]
        const minIndex = land[index+1]?.indexOf(Math.min(...land[index+1]))

        index += 1
    
        type = typeDict[type]
        
        if(type === "first"){
            sum += first
            for(let i =0; i<4; i++){
                if(i==0 || i===minIndex) continue
                callback(index,  i, sum)
            }
        }
        if(type === "second"){
            sum += second
            for(let i =0; i<4; i++){
                if(i==1 || i===minIndex) continue
                callback(index, i, sum)
            }
        }
        if(type === "third"){
            sum += third
            for(let i =0; i<4; i++){
                if(i==2 || i===minIndex) continue
                callback(index, i, sum)
            }
        }
        if(type === "fourth"){
            sum += fourth
           for(let i =0; i<4; i++){
                if(i==3 || i===minIndex) continue
                callback(index, i, sum)
            }
        }
        
    }
    return Math.max(...result)
}

 

---

 

올바른 풀이

시간을 줄일 방법이 생각나지 않아서 힌트를 얻었다. 

바로 DP를 사용하는 것이다.   

DP에대해서 잘 모른다면 꼭 공부하고 푸는 것을 추천한다. (DP 정리)

풀이를 간단하게 설명하자면 각각의 행마다 최대값이 될 수 있는 상황을 더하면서 내려가는 방식이다.

즉 바로바로 해당 열의 최대값을 구하는 것이다. 

 

 

 

위 문제의 예시는 아래와 같다 

최댓값 빨간색,  그다음으로 최댓값 파란색

이렇게 한 행을 지나칠 때마다  이전 행의 최대값을 더해준다 (단, 연속으로 같은 열은 불가능)

 

하드 코딩

function solution(land) {
  const length = land.length;

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

  return Math.max(...land[length - 1]);
}

 

 

정리한 코드

function solution(land) {
    const removeColumnUsed = (arr, index) => arr[index] = 0
    const getMaxScore = (row, index) => {
        const rowCopy = [...row]
        removeColumnUsed(rowCopy, index)
        return Math.max(...rowCopy)
    }
    
    for(let i = 1; i < land.length; i++) {
        land[i][0] += getMaxScore(land[i-1], 0)
        land[i][1] += getMaxScore(land[i-1], 1)
        land[i][2] += getMaxScore(land[i-1], 2)
        land[i][3] += getMaxScore(land[i-1], 3)
    }
    
    return Math.max(...land.at(-1))
}