JS알고리즘 | 격자판 최대합(2차원 배열)

문제

N*N 격자판이 주어지면 각 행의 합, 각 열의 합, 두 대각선의 합 중 가장 큰 합을 출력하세요.

 

입력예제 |

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

출력예제 | 

155

 

 

 

풀이

1. 각 행의 합, 각 열의 합 구한다. (합을 구해야할 때는 sum 변수 만들어주어야함. 여기서는 행의 합, 열의 합 필요해서 2개 선언)

2. 각 대각선의 합 구한다.

3. 비교해서 최대값을 구해서 answer에 넣는다. 

4. answer 출력

function solution(arr){
            let answer = Number.MIN_SAFE_INTEGER;
            // 1. answer는 최대값을 찾아야하니까 최소값으로 초기화 해놓는다. 
            let n = arr.length;
            let sum1 = 0;
            let sum2 = 0;
            // 행의 합은 sum1로 저장
            // 열의 합은 sum2로 저장
            // 행 탐색, 열 탐색을 이중for문으로
            for(let i = 0; i < n; i++){
                sum1 = 0;
                sum2 = 0;
                // for문이 한 번 끝날 때마다 매번 초기화를 시켜줘야한다.
                for(let j = 0; j < n; j++){
                    sum1 += arr[i][j]; // i가 돌고 j 고정(i기준 j의 모든 값 더하여 누적)
                    sum2 += arr[j][i]; // j가 돌고 i 고정(j기준 i의 모든 값 더하여 누적)
                    // 행이 돌고 열이 고정된다
                }
                answer = Math.max(answer, sum1, sum2); 
                // 최대값 구하는 메소드
            }
            
            // 이제 대각선의 합 구하는 for문 작성
            // 새로 대각선 합 구해야해서 초기화 해주어야한다.
            sum1 = 0; 
            sum2 = 0;
            for(let i = 0; i < n; i++){
                sum1 = arr[i][i]; // 똑같은 인덱스의 행과 열 
                sum2 = arr[i][n-i-1]; // sum1과 대칭인 값을 구해주어야한다.
            }
            answer = Math.max(answer, sum1, sum2);
            return answer;
    }
        

llet 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));

행과 열을 같이 탐색해야하므로 이중for문을 사용해준다.

행 -> i / 열 -> j

function solution(arr){
        let answer;
        let n = arr.length;
        let sum1 = 0;
        let sum2 = 0;
        for(let i = 0; i < n; i++){
            sum1 = 0;
            sum2 = 0;
            for(let j = 0; j < n; j++){
                sum1 += arr[i][j];
                sum2 += arr[j][i];
            }
            answer = Math.max(sum1, sum2);
        }
        sum1 = 0;
        sum2 = 0;
        for(let i = 0; i < n; i++){
                sum1 += arr[i][i];
                sum2 += arr[i][n-i-1];
        }
        answer = Math.max(sum1, sum2);
        return answer;
    }

        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));

answer에 가장 작은 정수를 써주지 않고도 작성이 가능하다.

 

여기서 더 알아보아야할 개념! 

for문이 돌때마다 sum 변수를 초기화해주는 것.

자바스크립트 스코프 개념 정리할 것

 

 

 

알게된 개념

2차원 배열

배열안에 또 다른 배열이 있는 것 

2차원 배열은  행과 열이 있다. 

행과 열이 있을때, 행부터 써준다.

arr[행][열]