격자판 합 구하기

:raising_hand: 알고리즘 공부 간 기록이 필요한 문제들에 대한 정리를 기록하는 포스트 입니다.

1. 문제 요건

N X N 2차원 배열을 주어지고 행,열,대각선의 합 중 가장 큰 부분을 구하여라

2. 코드

먼저 문제를 보자마자 기억나는 아이디어는 합을 모두 구해서 배열에 담고 비교하자 였다.

그래서 보자마자 아래와 같이 빠르게 작성을 해보았다.

  • 단순 비교

function solution(arr) {
    let n = arr.length // 길이
    // 신규배열 생성(등수초기화) 및 1로 초기화
    let tarr = Array.from({length: n}, () => 1) 
    for(let i=0; i < n; i++) { // 실제 arr 배열 값 특정
        for(let j=0; j < n; j++) { // arr 값(i) 에 대해 큰값 확인
            if(arr[i] < arr[j]) {  // arr[i] 값 보다 크면 등수 업
                tarr[i]++
            }
        }
    }
    return tarr
}

let arr = [87, 86, 92, 100, 76]

그리고 풀고나니 궂이 배열에 넣기 보단 max 함수를 사용한다면 간단하게 비교할 수 있겠다? 싶은 생각이 들어 아래와 같이 다시 짜보았다.

  • max 함수 적용

function solution2(arr) {
    let rowSum = middleSum = middleSum2 = heightSum = 0
    let max = Number.MIN_SAFE_INTEGER
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            rowSum += arr[i][j]
            heightSum += arr[j][i]
            if (i === j) {
                middleSum += arr[i][j]
            } 
            if ((i+j) === 4) {
                middleSum2 += arr[i][j]
            }
        }
        max = Math.max(max, rowSum, heightSum, middleSum)
        rowSum = heightSum = 0
    }
    return max
}
  • Solution

function solution3(arr) {
        let answer = Number.MIN_SAFE_INTEGER;
        let n = arr.length;
        let sum1 = sum2 = 0;
        for (let i = 0; i < n; i++) {
            sum1 = sum2 = 0;
            for (let j = 0; j < n; j++) {
                sum1 += arr[i][j];
                sum2 += arr[j][i];
            }
            answer = Math.max(answer, sum1, sum2);
        }
        sum1 = 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;
}

3. 결과정리

N X N 2차원 배열의 합을 연습해보는 문제를 풀었다. 먼저 이런 유형의 문제에서 기록해야 할 포인트는 다음과 같다.

아래 두 가지에 대한 포인트를 기억하자.

1. 모든 행을 단순 비교하여 한번에 구할 필요가 없다.
2. 솔루션 코드테서 볼 수 있듯이 열, 행의 합을 구하고 
다음 반복문을 통해 양 대각선의 합을 구한다.

어떻게 보면 나의 경우 if 조건을 2 * n ^ 2 번 체크 하게지만 아래 코드의 경우는 아얘 양 대각선을 특정한 반복문이기 때문에 필요없는 조건을 체크 할 필요가 없다.

You may also enjoy