[JS] - 격자판의 최대합 구하기

 

주어진 이차원 배열에서 
가로, 세로, 대각선의 합을 구해서 가장 큰 값을 출력하는 알고리즘

 

// 주어진 배열 
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],
];

주어진 배열에 가로, 세로 , 대각선의 합을 구하여서 

가장 큰 합을 구하라고 한다....

이게 도대체 무슨...????? 

 

대략 처음에 문제를 파악할 때는 일단 이중for문을 써야할 거 같다. 

 

그러면 처음에 내가 짠 코드를 보자 . 

function solution(arr){
	let answer = 0;
    let n = arr.length ;
    
    let sum = 0;
    for(let i = 0 ; i < n ; i ++){
    	for(let j = 0 ; j < n ; j ++){
        	sum += arr[i][j];
        }
    }
    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));

그렇다....

더이상 진도가 나가지 않는다.

굴려야 할 머리가 돌아가지를 않는다.

결국 해당 강의를 보고 해결을 보기는 했다.

어쩜 신기하게도 강의를 보면 참 이해가 잘된다. 

 

일단 

행과 열의 합을 구하는것은 너무도 당연한 이야기

마무리 대각선까지 구해야 해결이 난다. 

 

결론은???? 

function solution(arr) {
  let answer = Number.MIN_SAFE_INTEGER;
  let n = arr.length;

  let sum1 = 0; // 행의 합을 담을 변수
  let sum2 = 0; // 열의 합을 담을 변수 
  
  // 각 행, 열
  for (let i = 0; i < n; i++) {
  	// i번째 행이 새로 돌때 마다 각 sum 변수를 초기화해주어야한다!!!!
    sum1 = 0; 
    sum2 = 0;
    for (let j = 0; j < n; j++) {
      sum1 += arr[i][j];
      sum2 += arr[j][i];
    }
    
    // 가장 큰 수를 결과값에 담는다. 
    answer = Math.max(answer, sum1, sum2);
  }
  // 대각선
  // 이때도 마찬가지로 각 sum 변수는 초기화 해준다. 
  sum1 = 0;
  sum2 = 0;
  for (let i = 0; i < n; i++) {
    sum1 += arr[i][i];
    sum2 += arr[i][n - i - 1];
  }
  
  // 대각선까지 체크하고 다시 가장 큰 수를 결과값에 담는다. 
  answer = Math.max(answer, 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));

// 결과값
// 155

 

 

 

출처 - 인프런 자바스크립트 알고리즘 김태원님 강의