땅따먹기
문제 설명
땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(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입출력 예 설명
입출력 예 #1
문제의 예시와 같습니다.
해결한 나의 코드
function solution(land){
var answer = 0
var one = 0
var two = 0
var three = 0
for(var i=1; i<land.length; i++){
for(var j=0 j<4; j++){
if(j==0){
one = land[i-1][j+1] + land[i][j]
two = land[i-1][j+2] + land[i][j]
three = land[i-1][j+3] + land[i][j]
} else if(j==1){
one = land[i-1][j-1] + land[i][j]
two = land[i-1][j+1] + land[i][j]
three = land[i-1][j+2] + land[i][j]
} else if (j==2){
one = land[i-1][j-2] + land[i][j]
two = land[i-1][j-1] + land[i][j]
three = land[i-1][j+1] + land[i][j]
} else {
one = land[i-1][j-3] + land[i][j]
two = land[i-1][j-2] + land[i][j]
three = land[i-1][j-1] + land[i][j]
}
land[i][j] = Math.max(one, two, three)
}
}
answer = Math.max.apply(null, land[land.length-1])
return answer
}나의 알고리즘
사실 다소 무식(?)한 방법으로 해서 민망하다..
1번째 인덱스 행의 원소 값을 0번째 인덱스 행의 원소 값과 더해 최댓값을 구한다.
1-1. ※단, 열이 다른 원소와 합한 값 중 최댓값이어야 한다.
1-2. 예를 들어 위에서 나온 문제의 예를 들어보면,| 1 | 2 | 3 | 5 |
| 5 | 6 | 7 | 8 |
| 4 | 3 | 2 | 1 |저 5를, 열이 같은 1을 제외하고 2, 3, 5를 합해보면, {7, 8, 10} 이 나온다.
{7, 8, 10} 중 최댓값은 10이다. 따라서 5를 10으로 바꿔준다.| 1 | 2 | 3 | 5 |
| 10 | 6 | 7 | 8 |
| 4 | 3 | 2 | 1 |이번엔 6을 해보자. 6과 열이 같은 2를 제외하고 1, 3, 5를 합해보면, {7, 9, 11}이 나온다.
{7, 9, 11} 중 최댓값은 11이다. 따라서 6을 11로 바꿔준다.| 1 | 2 | 3 | 5 |
| 10 | 11 | 7 | 8 |
| 4 | 3 | 2 | 1 |7도 열이 같은 3을 제외하고 1, 2, 5를 합해보면, {8, 9, 12}가 나온다. 최댓값인 12로 바꿔준다.
| 1 | 2 | 3 | 5 |
| 10 | 11 | 12 | 8 |
| 4 | 3 | 2 | 1 |8도 열이 같은 5를 제외하고 1, 2, 3을 합해보면, {9, 10, 11}이 나온다. 최댓값인 11로 바꿔준다.
| 1 | 2 | 3 | 5 |
| 10 | 11 | 12 | 11 |
| 4 | 3 | 2 | 1 |
2번째 인덱스 행의 원소 값을 1번째 인덱스 행의 원소 값과 더해 최댓값을 구한다.
2-1. 위 과정과 동일하게 계산한다. 계산해보면| 1 | 2 | 3 | 5 |
| 10 | 11 | 12 | 11 |
| 16 | 15 | 13 | 13 | <- 이렇게 합이 누적된다.
- 합이 모두 누적되었다는 사실을 이용하여, 맨 마지막 행의 최댓값을 구한다.
본래 알고리즘은 이러하나, 코드화 할 때
- 만약 열이 0이면 -> 1,2,3열만 계산
- 만약 열이 1이면 -> 0,2,3열만 계산
- 만약 열이 2이면 -> 0,1,3열만 계산
- 만약 열이 3이면 -> 0,1,2열만 계산
이런 식으로 다소 무식(?)하게 풀었다 ㅋㅋㅋㅋㅋ
다른 사람의 코드
function solution(land) {
var answer = 0;
let before = 0;
for(let i=0 ; i<land.length-1 ; i++){
land[i+1] = max(land[i],land[i+1]);
}
answer = Math.max(...land[land.length-1])
return answer;
}
function max(arr1,arr2){
let stack = [];
let newArr = [0,0,0,0];
for(let i=0 ; i<arr2.length ; i++){
for(let j=0 ; j<arr1.length ; j++){
if(j === i) continue;
stack.push(arr1[j]+arr2[i])
}
newArr[i] = Math.max(...stack);
stack = [];
}
return newArr;
}일단 앞의 행과 뒤의 행에 해당하는 배열을 받아서 열이 같은 원소를 제외(continue)하고 더한 값의 최댓값을 넣은 배열을 반환해주는 함수를 만들어서 그 뒤의 행 자체를 바꿔주는 식으로 구현한 것 같다.
그런 다음 배열 원소들의 최댓값을 구해 answer로 반환해주는 것.
유사한 문제를 풀어본 게 도움이 되었던 것 같다 - 가장 큰 정사각형 찾기
코테 문제는 진짜 적더라도 꾸준히 푸는게 좋을 것 같다. 다른 바쁜 일로 제쳐두면 이제껏 쌓은 감 완전 잃을 수 있겠다는 생각이 .. !!
