[배열탐색] 격자판 최대합

자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다.

 

 

 

 

📋 문제

N*N의 격자판이 주어지면 각 행의 합, 각 열의 합, 두 대각선의 합 중 가장 큰 수를 출력한다.

 

 

👉 입력

N줄에 걸쳐 N개의 자연수가 주어진다.

각 자연수는 100을 넘지 않는다.

 

 

👈 출력

최대 합을 출력한다.

 

 

📝 풀이

 

function solution(arr) {
    let n = arr.length;
    let sum_row = sum_col = sum_diag1 = sum_diag2 = 0;
    let sums = [];

    for (let i = 0; i < n; i++) {
        sum_row = sum_col = 0;
        for (let j = 0; j < n; j++) {
            if (i === j) sum_diag1 += arr[i][j];
            if (i + j === n - 1) sum_diag2 += arr[i][j];
            sum_row += arr[i][j];
            sum_col += arr[j][i];
        }
        sums.push(sum_row, sum_col)
    }
    sums.push(sum_diag1, sum_diag2)
    return Math.max(...sums);
}

let arr = [[10, 13, 10, 12, 15],
[12, 39, 30, 23, 11],
[11, 25, 50, 53, 15],
[19, 27, 29, 37, 27],
[19, 13, 30, 13, 19]];
console.log(solution(arr));

 

행, 열, 왼쪽 위에서 오른쪽 아래의 대각선, 오른쪽 위에서 왼쪽 아래의 대각선을 뜻하는 변수 sum_row, sum_col, sum_diag1, sum_diag2을 선언하고 0으로 초기화한다.

이들을 저장할 sums라는 빈 배열을 선언한다.

 

이중 for문을 돌며 각 행의 합과 각 열의 합을 sum_row, sum_col에 저장한다.

이때 다른 조건으로 i와 j의 값이 동일하면 sum_diag1에 값을 더하고 i + j의 값이 n -1과 같으면 sum_diag2에 값을 더한다.

안쪽 for문을 끝낼 때마다 행의 합과 열의 합을 sums에 넣어주고 0으로 초기화한다.

바깥쪽 for문도 순회가 끝나면 두 대각선의 합을 sums에 넣어준다.

이후 Math.max()를 이용해 sums의 요소 중 제일 큰 수를 출력한다.