[1,2차원 배열 탐색][JS] 격자판 최대합

격자판 최대합

---

문제 설명

5x5 격자판에 아래롸 같이 숫자가 적혀있습니다.

NxN의 격자판이 주어지면 각 행의 합, 각 열의 합, 두 대각선의 합 중 가 장 큰 합을 출력합 니다.

제한 사항

없음

입력 설명

첫 줄에 자연수 N이 주어진다.(1<=N<=50)
두 번째 줄부터 N줄에 걸쳐 각 줄에 N개의 자연수가 주어진다. 각 자연수는 100을 넘지 않는 다.

출력 설명

최대합을 출력합니다.

입출력 예제

▣ 입력예제 1

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

▣ 출력예제 1

• 155

---

해답/풀이

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

  let raw = (column = 0);

  for (let i = 0; i < n; i++) {
    raw = column = 0;
    for (let j = 0; j < n; j++) {
      raw += arr[i][j];
      column += arr[j][i];
    }

    answer = Math.max(answer, raw, column);
  }

  let diagonal = (reDiagonal = 0);
  for (let i = 0; i < n; i++) {
    diagonal += arr[i][i];
    reDiagonal += arr[i][n - i - 1];
  }

  answer = Math.max(answer, diagonal, reDiagonal);

  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

수도 코드

function solution(arr) {
  // 0. 5개의 배열의 요소를 담은 하나의 배열 arr를 매개변수로 받는다.
  // 1. 비교군의 기준이 될 가장 작은 값을 초기값으로 설정한다.
  let answer = Number.MIN_SAFE_INTEGER;

  // 2. 행과 열 중에 가장 큰 값을 구하기
  // 3. 행과 열의 값을 누적하는 변수를 설정한다.
  let raw = 0; // 행
  let column = 0; // 열

  // 4. 배열 안의 배열 요소를 이중 for 문을 이용해서 반복-탐색한다.
  for (let i = 0; i < arr.length; i++) {
    // 5. 배열 안의 배열 요소를 각각 비교한다.
    // 5.1 한 행과 열을 돌 때마다 0으로 초기화 해준다.
    let raw = 0; // 행 초기화
    let column = 0; // 열 초기화

    // 5.2 두 번째 for 문을 돌며 각각의 요소를 돈다.
    for (let j = 0; j < arr.length; j++) {
      /*
       * 5.1.1 행(가로)으로 왼쪽에서 오른쪽으로 한 행씩 더해준다.
       * => 10 + 13 + 10 + 12 + 15(1행 끝) => 115 => 행의 index 0번째로 초기화
       * => 12 + 30 + 30 + 23 + 11(2행 끝) => 154 => 행의 index 0번째로 초기화
       * => ... 행을 다 돌 때까지 반복.
       */
      raw += arr[i][j];

      /*
       * 5.1.2 열(세로)로 첫번째 칸에서 아래 칸까지 한 열씩 더해준다.
       * => 10 + 12 + 11 + 19 + 19(1열 끝) => 117 => 열의 index 0번째로 초기화
       * => 13 + 39 + 25 + 27 + 13(2열 끝) => 149 => 열의 index 0번째로 초기화
       * => ... 열을 다 돌 때까지 반복.
       */
      column += arr[j][i];
    }
    // 6. 행과 열 중에서 가장 큰 값을 구하고 그것을 answer에 누적한다.
    // 6.1 가장 큰 값만 누적된 answer를 Math.max에 포함한다.
    // 6.2 결국 가장 큰 값이 answer에 최종적으로 누적된다.
    answer = Math.max(answer, raw, column);
  }

  // 7. 왼쪽 대각선과 오른쪽 대각선 중에 가장 큰 값을 구하기
  // 8. 왼쪽 대각선과 오른쪽 대각선의 값을 누적하는 변수를 설정한다.
  let diagonal = 0; // 왼쪽 대각선
  let reDiagonal = 0; // 오른쪽 대각선

  // 9. 배열 안의 배열 요소를 for 문을 이용해서 반복-탐색한다.
  for (let i = 0; i < arr.length; i++) {
    // 10. 배열 안의 배열 요소를 비교한다.

    /*
     * 11.1 `diagonal`는 배열의 0 번째부터 시작하는 열과 행이 만나는 지점(arr[i][i])만 돌며 더해준다.
     * ex) arr[0][0], arr[1][1], arr[2][2] ...
     * => 10 + 39 + 50 + 37 + 19(diagonal 끝)
     */
    diagonal += arr[i][i];

    /*
     * 11.2 `reDiagonal`는 배열의 i번째의 가장 끝 대척점 부터 시작하는 열과 행이 만나는 지점(arr[i][arr.length - i - 1])만 돌며 더해준다.
     * ex) arr[0][5-0-1], arr[1][5-1-1], arr[2][5-2-1] ...
     * => 15 + 23 + 50 + 27 + 19(reDiagonal 끝) => 134
     */
    reDiagonal += arr[i][arr.length - i - 1];
  }

  // 12. diagonal 와 reDiagonal 중에서 가장 큰 값을 구하고 그것을 answer에 누적한다.
  // 12.1 가장 큰 값만 누적된 answer를 Math.max에 포함한다.
  // 12.2 결국 가장 큰 값이 answer에 최종적으로 누적된다.
  answer = Math.max(answer, diagonal, reDiagonal);

  // 13. 가장 큰 값을 담은 answer를 반환한다.
  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

풀이 순서

let answer = Number.MIN_SAFE_INTEGER;
let n = arr.length;

• 비교 값으로 넣어줄 최솟값 anwser에 Number.MIN_SAFE_INTEGER; 할당.
• 행의 합 raw, 열의 합 column 변수를 만들고 초기값 0 설정.

let raw = (column = 0);

for (let i = 0; i < n; i++) {
  raw = column = 0;

  for (let j = 0; j < n; j++) {
    raw += arr[i][j];
    column += arr[j][i];
  }
  answer = Math.max(answer, raw, column);
}

• 행과 열의 최대값을 얻기 위한 이중 for문 작성
• 이중 for문 사이에 첫 번째 for문이 돌 때마다 raw와 column을 초기화함.
• raw는 행 번호가 고정되고, 열 번호가 증가할 수 있도록 arr[i][j]를 더해줌. 행이 누적하는 결과.
• column는 열 번호가 고정되고, 행 번호가 증가할 수 있도록 arr[j][i]를 더해줌. 열이 누적하는 결과.
• answer에 Math.max() 메소드를 사용하여 answer와 raw와 column 중 최대 값을 구함.

let diagonal = (reDiagonal = 0);
for (let i = 0; i < n; i++) {
  diagonal += arr[i][i];
  reDiagonal += arr[i][n - i - 1];
}

• 배열의 0 번째부터 시작하는 대각선인 diagonal, 배열의 가장 마지막에서부터 시작하는 reDiagonal 변수를 만들고 초기값 0 설정.
• 대각선의 최대값을 얻기 위한 for문 작성
• diagonal는 배열의 0 번째부터 시작하는 열과 행이 만나는 지점만 찾아야 하기 때문에 arr[i][i]를 더해줌.
• reDiagonal는 배열의 가장 마지막 번째부터 시작하는 열과 행이 만나는 지점만 찾아야 하기 때문에 arr[i][n - i - 1]를 더해줌.

answer = Math.max(answer, diagonal, reDiagonal);

• answer에 Math.max() 메소드를 사용하여 answer와 diagonal와 reDiagonal 중 최대 값을 구함.

⚡️ Resource

---

Math.max() 메서드

• Math.max()함수는 입력 값으로 받은 0개 이상의 숫자 중 가장 큰 숫자를 반환합니다.

MDN 공식 문서 : Math.max()

Example

console.log(Math.max(1, 3, 2));
// expected output: 3

console.log(Math.max(-1, -3, -2));
// expected output: -1

const array1 = [1, 3, 2];

console.log(Math.max(...array1));
// expected output: 3

⚡️ Reference

---

✍🏻 자바스크립트 알고리즘 문제풀이 - 인프런