[코딩테스트]프로그래머스 - 땅따먹기

Adela·2020년 5월 19일
0

프로그래머스

목록 보기
13/30
post-thumbnail

땅따먹기

문제 설명

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(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. 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 |

  1. 2번째 인덱스 행의 원소 값을 1번째 인덱스 행의 원소 값과 더해 최댓값을 구한다.
    2-1. 위 과정과 동일하게 계산한다. 계산해보면

    | 1 | 2 | 3 | 5 |
    | 10 | 11 | 12 | 11 |
    | 16 | 15 | 13 | 13 | <- 이렇게 합이 누적된다.

  1. 합이 모두 누적되었다는 사실을 이용하여, 맨 마지막 행의 최댓값을 구한다.

본래 알고리즘은 이러하나, 코드화 할 때

  1. 만약 열이 0이면 -> 1,2,3열만 계산
  2. 만약 열이 1이면 -> 0,2,3열만 계산
  3. 만약 열이 2이면 -> 0,1,3열만 계산
  4. 만약 열이 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로 반환해주는 것.

유사한 문제를 풀어본 게 도움이 되었던 것 같다 - 가장 큰 정사각형 찾기

코테 문제는 진짜 적더라도 꾸준히 푸는게 좋을 것 같다. 다른 바쁜 일로 제쳐두면 이제껏 쌓은 감 완전 잃을 수 있겠다는 생각이 .. !!

profile
개발 공부하는 심리학도

0개의 댓글