2021.7.31 TIL (격차판 최대합, 봉우리)

문제) n:n 격차판 최대 합 구하기

n:n격자판의 가로/세로/대각선 합 중에서 최대값 구하기

 

function solution(arr) {
  let answer;
  // code here;
  return answer;
}

let example = [
  [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(example)) // 155

 

 

나의 조잡한 해답) 가로/세로/대각선1/대각선 2의 합을 구하고, 비교한다.

 

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

  //가로 합의 최대값 구하기
  for(let el of arr) {
    let sum += el.reduce((a, b) => b += a, 0);
    Math.max(answer, sum);
  };

  //세로 합의 최대값 구하기
  for(let i = 0; i < n ; i++) {
    let sum = 0;
    for(let j = 0; j < n; j++) {
      sum += arr[j][i];
    }
         Math.max(answer, sum);
  }

  //대각선 2개의 합 구하기
  for (let i = 0; i < n ; i ++) {
    dia1 += arr[i][i];
    dia2 += arr[i][n-i-1];
  }

  answer = Math.max(answer, dia1, dia2);
  return answer;
}

 

 

선생님의 보다 깔끔한 답) 가로와 세로를 하나로 묶는다.

 

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

  //가로와 세로 합의 최대값 구하기
  for(let i = 0; i < n ; i++) {
    for(let j = 0; j < n; j++) {
      sum1 += arr[i][j]; //가로
      sum2 += arr[j][i]; //세로
    }
         Math.max(answer, sum1, sum2);
  }

  //대각선 2개의 합 구하기
  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;
}

 

 

결론: 모를 때는 경우의 수를 하나하나씩 나열하면서 규칙을 찾을 것

 

# 세로의 합 중에서 최대값을 구하기
/**
 * arr[0][0] + arr[1][0]+ ... + arr[n][0]
 * arr[1][0] + arr[1][1] + ... + arr[n][1]
 * ...
 * arr[n][0] + arr[n][1] + ... + arr[n][n]
 * => arr[순차적으로 돌아감][고정]
 */

 

 

 

문제 ) 봉우리는 몇개일까?

2차원 배열이 주어질 때, 상하좌우의 값보다 클 경우 봉우리가 된다.

 

function findPeaks(arr) {
  let answer;
  // code here;
  return answer;
}

let example = [
  [5, 3, 7, 2, 3],
  [3, 7, 1, 6, 1],
  [7, 2, 5, 3, 4],
  [4, 3, 6, 4, 1],
  [8, 7, 3, 5, 2]
];

console.log(findPeaks(example)) // 10

 

 

모를 땐 하나씩 해본다.

 

/**
 * a[1][1] 상하좌우 비교하기
 * a[1][1] > (a[0][1], a[1][0], a[1][2], a[2][1])
 * 일반화 해보면..
 * a[i][j] > (a[i-1][j], a[i][j-1], a[i][j+1], a[i+1][j])
 * 주의할 점 괄호안의 숫자는 0 또는 자연수여야 한다.
 * a[0][0] 은 위의 방법으로 하기 힘들어 보인다..
 * example에 0으로 둘러쌓인 배열을 앞뒤로 넣으면 어떠할까?
 * [
 *  [0,0,0,0,0,0,0]
 *  [0,5,3,7,2,3,0]
 *       ...
 *  [0,0,0,0,0,0,0]
 * ]
 */

 

 

나의 답)

1-depth 이상인 배열에선 추천하지 않는다. 깊은 복사도, 그 차원의 깊은 복사만 하기 때문이다. 예를 들면, let arr = [1, 2, ['a']] 인 배열을 깊은 복사해보자. let newArr = arr.slice() 한 뒤 newArr[2][0]='b' 변경한 후에 console.log(arr[2][0], newArr[2][0]) // 둘다 'b' 를 출력한다는 것을 알 수 있다.

 

function findPeaks(arr) {
  let answer = 0;
  let n = arr.length;
  let temp = arr.slice(); //깊은 복사
  let zeros = Array.from({length:n + 2}, () => 0);
  // n = 5일 때, zeros = [0,0,0,0,0,0,0]

  //arr를 0으로 감싼다.
  for(let i = 0; i < n ; i++) {
    let newEl = temp[i].slice(0);
    newEl.push(0);
    newEl.unshift(0);
  }
  temp.push(zeros);
  temp.unshift(zeros);

  //변형된 배열을 하나씩 돌아가며 상하좌우 요소들과 크기를 비교한다.
  for(let i = 1; i < n+1; i++) {
    for(let j = 1; j < n+1; j++) {
      let current = arr[i][j]
      let aroundMax = Math(arr[i-1][j], arr[i][j+1], arr[i+1][j], arr[i][j-1]);
      if(current > aroundMax) {
        answer++;
      }
    }
  }

  return answer;
}

 

 

선생님의 답)

 

/**
* a[1][1]일 때,
* a[1 - 1][1 + 0], a[1 + 0][1 + 1], a[1 + 1][1 + 0], a[1 + 0][1 - 1] 과 비교하면 된다.
* 즉, 가로축 [-1, 0, 1, 0], 세로축 [0, 1, 0, -1]을 더하거나 빼주면 된다.
*/

 

 

function findPeaks(arr) {
  let answer = 0;
  let n = arr.length;
  let dx = [-1, 0, 1, 0];
  let dy = [0, 1, 0, -1];

  for(let i = 0; i < n; i++) {//가로축
    for(let j = 0; j < n; j++) {//세로축
      for(let k = 0; k < dx.length; k++) {
        let nx = i + dx[k];
        let ny = j + dy[k];
        if(nx > 0 && nx <n && arr[nx][ny] >= arr[i][j]) {
          answer++;
        }
      }
    }
  }

  return answer;
}