[알고리즘]2D Array - DS

문제 링크

https://www.hackerrank.com/challenges/2d-array/problem?h_r=profile

풀이

이 문제는 주어진 2차원 배열을 쭉 읽으면서 모래시계 모양이 나오는 모든 부분의 합을 기록하여 그 중 최대값이 몇인지를 묻는 문제이다.

[0][0]부터 모래시계의 좌측 상단이라고 가정한 뒤 한 행을 쭉 계산하면 되는데, 모래시계의 변 길이가 3이었으므로 배열의 길이-2의 위치까지만 진행하면 된다.(열도 마찬가지이다.)

전체 배열의 계산이 끝났으면 getMax()를 통해 2차원 배열의 최댓값을 구하여 반환한다.

getMax()는 2차원 배열을 spread연산자를 사용하여 1차원 배열로 풀어버린 다임 각 1차원 배열마다 재귀로 getMax()를 부르게 된다. 그렇게 되면 1차원 배열은 spread연산자로 값으로 풀리게 되고 Array.isArray()에 의해 배열이 아니기 때문에 그냥 자신의 값을 반환하게 된다. 그렇게 반환된 값들 중 제일 큰 값을 반환하는 방식이다.

1. 2차원 배열을 1차원 배열로 분해
2. 1차원 배열을 값으로 분해하여 최댓값 반환
3. 2에서 구해진 각 1차원 배열의 최댓값 중 다시 최댓값을 구해 반환(2차원 배열 내 최댓값)

이번 문제에서는 getMax() 함수가 가장 큰 수확이 아니었나싶다. 평소 같았으면 2중 for문 돌면서 하나씩 체크했을텐데, 왠지 될 거 같아서 시도한 방법이 잘 작동해서 기분이 좋다. 체크는 해보지 않았지만, 결국 2차원 배열의 값을 모두 풀어서 최대값을 비교하는 거라 성능상의 이득은 잘 모르겠다.

코드

function getSum(arr, x, y)
{
    let sum = 0;
    for(let i = x; i < x + 3; i++)
    {
        sum+=arr[y][i] + arr[y+2][i];
    }
    return sum+=arr[y+1][x+1];
}

function getMax(arr) //2차원 배열 내 최댓값
{
    return Math.max(...arr.map(sub=>Array.isArray(sub)?getMax(sub):sub));
}

function hourglassSum(arr) { //문제
    // Write your code here
    let sumArr=[];
    for(let i = 0; i < arr.length - 2; i++)
    {
        sumArr[i] = new Array();
        for(let j = 0; j < arr[i].length - 2; j++)
            sumArr[i].push(getSum(arr, j, i));
    }
    return getMax(sumArr);
}