2차원 배열 - 봉우리

행렬의 요소를 순회하면서 상하좌우값을 비교해 이들보다 크다면 봉우리가 되는 문제이다.

 

나의 풀이

function solution(arr) {
  let result = 0;
  const n = arr.length;
  const formatted = arr.map((list) => [0, ...list, 0]);
  formatted.push(Array.from({ length: n + 2 }).fill(0));
  formatted.unshift(Array.from({ length: n + 2 }).fill(0));

  for (let i = 1; i < formatted.length - 1; i += 1) {
    for (let j = 1; j < formatted.length - 1; j += 1) {
      if (
        formatted[i][j] > formatted[i][j + 1] &&
        formatted[i][j] > formatted[i][j - 1] &&
        formatted[i][j] > formatted[i + 1][j] &&
        formatted[i][j] > formatted[i - 1][j]
      ) {
        result += 1;
      }
    }
  }

  return result;
}

let arr = [
  [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(solution(arr));

 

행렬의 가장자리는 0으로 초기화 되었다고 가정했기 때문에, 다음 그림과 같이 감싸기 위해 입력값에 배열과 요소를 추가했다.

0	0	0	0	0	0	0
0						0
0						0
0						0
0						0
0						0
0	0	0	0	0	0	0

 

그리고 테두리는 상하좌우값을 비교할 필요가 없기 때문에 입력값 범위의 인덱스 내부에서만 상하좌우의 값을 비교하도록 코드를 구현했다.

 

다른 풀이

function solution(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++) {
      let flag = 1;
      for (let k = 0; k < 4; k++) {
        let nx = i + dx[k];
        let ny = j + dy[k];
        if (nx >= 0 && nx < n && ny >= 0 && ny < n && arr[nx][ny] >= arr[i][j]) {
          flag = 0;
          break;
        }
      }
      if (flag) answer++;
    }
  }

  return answer;
}

let arr = [
  [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(solution(arr));

 

이 풀이의 핵심은 상하좌우 값을 비교하기위해서 현재 위치의 행과 열의 인덱스에 어떤 값을 더하거나 빼야할지를 배열로 구현한 것이다.

 

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

 

예를 들어 현재 색칠한 1의 상하좌우의 값들은 행과 열의 인덱스로 표현할 수 있다.

현재 1이 위치한 지점을 arr[x][y]라고 표현한다면 상하좌우는 다음과 같이 표현할 수 있다.

- 상 : arr[x-1][y]

- 하 : arr[x+1][y]

- 좌 : arr[x][y-1]

- 우 : arr[x][y+1]

 

이것을 현재 위치에서 행의 인덱스에 더해야하는 값과 열의 인덱스에 더해야하는 값들의 배열로 표현하면 다음과 같다.

  let dx = [-1, 0, 1, 0];
  let dy = [0, 1, 0, -1];

 

즉, 현재 행의 위치인 (x,y)에서 "상"에 해당하는 위치는 행의 인덱스에 -1을 하고 열의 인덱스는 그대로 유지해야한다.

"좌"에 해당하는 위치는 행의 인덱스는 그대로 두고 열의 인덱스를 -1 해야한다. 

 

for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      let flag = 1;
      for (let k = 0; k < 4; k++) {
        let nx = i + dx[k];
        let ny = j + dy[k];
        if (nx >= 0 && nx < n && ny >= 0 && ny < n && arr[nx][ny] >= arr[i][j]) {
          flag = 0;
          break;
        }
      }
      if (flag) answer++;
    }

 

그리고 행렬을 순회하면서 상하좌우 총 4번 반복하며 현재 위치한 값보다 큰 값이 있으면 flag를 0으로 바꿔준다.

여기서 조건이 하나 더 추가되는데 테두리에 있는 값들은 상하좌우를 비교할 때 인덱스에 데이터가 존재하지 않는 경우가 있다.

그렇기 때문에 상하좌우의 인덱스가 0보다 크면서 행렬의 크기보다는 작아야한다. 그렇지 않으면 arr[nx][ny]의 값에 참조할 수 없게된다.

행렬에 존재하는 값들만 살펴보겠다는 의미이다. 없는 값이면 배제한다.

 

느낀점

두번째 풀이로 풀게되면 새로운 배열을 생성해서 집어넣어줄 필요가 없게된다.

또한 상하좌우에 현재 위치의 값보다 큰 값을 만나게되면 반복문을 빠져나가니 상하좌우 전체 요소를 순회하지 않아도 된다.

 

시간이 지나고 다시 한 번 풀어보니 첫번째와 똑같은 풀이 밖에 생각나지 않았다...😂

다시 복습하면서 핵심을 정리하면,

 

- 조건에 맞지 않는 경우에 flag를 활용하기

- 상하좌우의 인덱스를 배열에 저장한 후, 루프를 통해 확인하기

- 범위에 존재하지 않는 요소는 배제하기

 

다시 풀었을 때 똑같이 틀리거나 풀이 방법에 진화가 없다면 아직 내 코드가 된 것이 아니고, 비슷한 문제를 만났을 때  똑같이 풀 수 밖에 없을 것이다.

많은 양을 복습없이 몰아치기보다 정해진 양을 풀고, 풀지 못한 부분에 대한 꼼꼼한 복습이 훨씬 효과적이라고 생각한다.

꾸준하게 복습하자.