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

# 문제 원문

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

예를 들면,

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |

로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

제한사항

• 행의 개수 N : 100,000 이하의 자연수
• 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.
• 점수 : 100 이하의 자연수

입출력 예

land / answer

[[1,2,3,5],[5,6,7,8],[4,3,2,1]]

16

 

# 문제 풀이

입력 받은 land의 row를 타고 내려가면서 row당 col 한개의 값들을 합한 값이 최대가 되는 값을 구하는 문제이다.

제약사항으로 동일한 col를 연속해서 선택 할 수 없다. 라는 내용이 있다. 해당 제약 사항으로 인해서 처음은 고민한게 어차피 first와 second 둘중 하나를 고르는 거니 먼저 row를 복사해서 sort하고 first와 second를 구해서 row과 경쟁이 되었을때 해당 row의 first와 second 둘 차이를 계산해서 가장 적은 수를 고르는 식으로 해당 조건이 최선이 되는 값들을 구하는 방향으로 생각하고 들어가보니 실제로 구현하려니 너무 귀찮았다.

그래서 이렇게 케이스를 모두 따지는거 보다는 그냥 단순히 그전 값들중 자신과 같은 col을 제외한 값중 최대값을 구하는 방향으로 전환해서 풀었다. 결과적으로는 first아니면 second를 선택하는건 똑같지만... 답이 간단한 편인데 실제로 구현 하려면 조금 고민할 필요가 있는 문제이다.

 

# 솔루션 플로우

1. 입력 받은 land의 row 1부터 끝까지 순회한다.(reduce를 사용해서 초기값으로 index 0을 생략했다.)

3. 해당 row의 각 col을 순회하면서 그전 row의 동일한 col를 제하고 최대값을 구한다.

4. 그 최대값과 해당 col의 값을 합산해서 해당 row까지의 result를 구한다.

3. 그렇게 구해진 result 중 최대값을 찾아서 반환한다.

1. FP

function solution(land) {
    return Math.max(...land.reduce((result, row, rdx) =>
        row.map((num, cdx) => {
            const state = Array.from(result);
            state[cdx] = 0;
            return num + Math.max(...state);
        })
    ));
}