[프로그래머스][Javascript]땅따먹기

문제

땅따먹기

프로그래머스

처음 문제를 풀 때 한 행에 값이 중복될 수 있다는 것을 고려하지 않고 풀어서 첫 번째 코드로는 통과되지 못했다. 

 

중복 생각 안 한 코드

function solution(land) {
    var answer = 0;
    let max;
    let index;
    for(let i in land){
        max = Math.max(...land[i]);
        index = parseInt(land[i].indexOf(max));
        if(land[parseInt(i)+1]){land[parseInt(i)+1][index] = 0;}
        answer += max;
    }
    return answer;
}

console.log(solution([[1,1,2,2],[1,2,4,0]]))

한 행에서 가장 큰 값을 구하고 answer에 합한다. 이다음 행에서 연속되는 인덱스 값을 0으로 만들어서 같은 인덱스가 선택되지 못하도록 한 코드이다. 한 행에 [1,1,1,2]같이 중복이 발생한다면 절대 정답이 나올 수 없는 코드이다...😭

 

land = [[2,2,2,1],[10,1,1,1]] 일 때
올바른 정답 : 12
중복을 고려하지 않은 코드 : 3

 

중복을 고려해서 코드를 짜려는 순간 너무 복잡해진다.ㅠㅜ

계속 고민한 끝에 다른 사람의 풀이 중 파이썬 코드가 직관적이고 이해하기 쉬웠다. 

바로 이 코드이다. 

 

파이썬코드...

def solution(land):

    for i in range(1,len(land)):
        for j in range(len(land[0])):
            land[i][j] += max(land[i-1][:j] + land[i-1][j+1:])

    return max(land[len(land)-1])

행을 돌면서 이전 행에서 연속되는 열을 제외한 요소 중 max값을  각 열에 더해 저장한다. 

이 코드를 활용하여 자바스크립트 코드로 작성해 봤다!

 

자바스크립트코드

//dp
function solution(land) {
    var answer = 0;
    let k ;
    let max;
    
    for(let i in land){
        if(i == 0){continue;} //첫번째 행은 통과
        for(let j in land[i]){
            k =[]
            k=k.concat(land[i-1]);  //배열 복사하는 코드
            k[j] = -1; //연속 되는 열은 제외하기 위해 음수를 넣어줌
            land[i][j] += Math.max(...k);
        }
        max =Math.max(...land[i]);
    }
    
    return max;
    
}

 

land배열의 행을 k배열에 복사하고 할 때

단순히 let k = land [i-1]을 하게 되면 동일한 객체를 가리키기 때문에 복사가 아니라 참조가 된다. 

따라서 k배열을 변경하는 순간 land [i-1] 배열도 변경되게 된다!

그래서 concat() 함수를 활용했다. 빈 k배열에 land [i-1] 배열을 합치는 식으로 복사를 했다. 

 

더 나은 방법은 없을까?

https://ecofreenavigator.tistory.com/22

자바스크립트(Javascript) 배열 복사 하는법

 

💡idea 요약

dp

for문을 돌면서 배열의 각 행에 각 열에 최대 결과값을 저장한다. 맨 마지막 행에 각 열에 결과값 중 가장 큰 값이 정답이 된다.

통과