[프로그래머스] 안전지대 (feat. 안전한 2차원 배열 초기화)

Chaejung·2023년 7월 25일
JavaScript알고리즘
0

알고리즘_JavaScript

목록 보기
8/12

문제

접근 방법

지뢰의 정보가 있는 board를 완전 탐색하면서 새롭게 지뢰와 지뢰 주변을 표시하는 2차원 배열을 만든다. 그리고 그 후 새롭게 만들어진 2차원 배열의 안전 지대의 개수를 카운트하면 된다.

그런데 배열을 다루는 데에 아직 미숙한 나머지 이 문제를 결국 풀지 못했다...

틀린 풀이

function solution(board) {
  const N = board.length;
  const dangerChecked = Array(N).fill(Array(N).fill(0));
  const di = [0, -1, -1, 0, 1, 1, 1, 0, -1];
  const dj = [0, 0, 1, 1, 1, 0, -1, -1, -1];
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (board[i][j] === 1) {
        Array.from({ length: 9 }, (_, idx) => idx).forEach((dIdx) => {
          let [newI, newJ] = [i + di[dIdx], j + dj[dIdx]];
          if ((0 <= newI) & (newI < N) & (0 <= newJ) & (newJ < N)) {
            dangerChecked[newI][newJ] = 1;
          }
        });
      }
    }
  }
  const safeAreaCount = dangerChecked.reduce(
    (a, b) => a + b.filter((cell) => cell === 0).length,
    0
  );
  return safeAreaCount;
}

분명히 로직은 틀린 게 없는데 dangerChecked[newI][newJ] = 1; 처리가 요상하게 되고 있었다.

한 칸만 1로 변하게 만들었는데, 왜 전체 column에 대해서 변하는 걸까?

그 이유는 바로 dangerChecked를 초기화할 때 썼던 Array(N).fill(Array(N).fill(0)에서 찾을 수 있었다.

처음에는 Array(N)가 새로운 Instance를 생성하면서 참조가 복사되는 건 줄 알았는데, 그게 아니라 fill(element)에서 element가 object인 경우 채워지는 각 슬롯 별로 동일한 참조를 향한다고 한다(call by reference) (출처)

그래서 2차원 배열(M*N)을 init 값으로 초기화할 시 fill()을 쓰고 싶은 경우 다음과 같이 수정하면 된다. (출처)

Array(M).fill(null).map(() => Array(N).fill(init));

null로 채워진 것을 map을 통해 새로운 배열을 반환하면서 fill의 인자에 object가 들어가지 않고, 원시 값인 init을 넣도록 처리했다.

맞는 풀이

function solution(board) {
  const N = board.length;
  // 여기만 다르다!!
  const dangerChecked = Array(N).fill(null).map(() => Array(N).fill(0));
  // 
  const di = [0, -1, -1, 0, 1, 1, 1, 0, -1];
  const dj = [0, 0, 1, 1, 1, 0, -1, -1, -1];
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (board[i][j] === 1) {
        Array.from({ length: 9 }, (_, idx) => idx).forEach((dIdx) => {
          let [newI, newJ] = [i + di[dIdx], j + dj[dIdx]];
          if ((0 <= newI) & (newI < N) & (0 <= newJ) & (newJ < N)) {
            dangerChecked[newI][newJ] = 1;
          }
        });
      }
    }
  }
  const safeAreaCount = dangerChecked.reduce(
    (a, b) => a + b.filter((cell) => cell === 0).length,
    0
  );
  return safeAreaCount;
}
평균 시간: 0.368ms
평균 메모리: 33.500MB
최고 시간: 0.57ms
최저 시간: 0.17ms
최고 메모리: 33.6MB
최저 메모리: 33.4MB
시간 표준 편차: 0.150
메모리 표준 편차: 8.969

배열을 안전하게 초기화 하는 방법

앞으로 이런 식으로 배열을 초기화할 일이 일어날텐데, 여러 방법으로다가 방법들을 숙지하는 게 좋겠다 싶어서 정리한다!

M * N을 init으로 초기화하는 방법

fill을 이용하는 경우

// way01
Array(M).fill(null).map(() => Array(N).fill(init));
// way02
new Array(M).fill(null).map(() => new Array(N).fill(init));

결과 상의 차이는 없으나 구분 지은 이유는 성능 상의 차이가 있다고 생각되어 적어둔다.
자세한 결과는 가장 아래에 정리해 놓았다.

from을 이용하는 경우

// way03
Array.from({ length: M }, () => Array(N).fill(init));
// way04
Array.from(Array(M), () => Array(N).fill(init));

spread 연산자를 이용하는 경우

// way05
[... Array(M)].map(elem => Array(N).fill(init))

for 문을 이용하는 경우

// way06
const intializedArray = (() => {
  let arr = [];
  for (let i = 0; i < M; i++){
    let row = []
    for (let j = 0; j < N; j++){
      row.push(init)
    }
    arr.push(row)
  }
  return arr;
})()
// way07
const intializedArray = (() => {
  let arr = [];
  for (let i = 0; i < M; i++) arr[i] = Array(N).fill(init);
  return arr;
})()
// way08
const intializedArray = (() => {
  let arr = Array(M);
  for (let i = 0; i < arr.length; i++) arr[i] = Array(N).fill(init);
  return arr;
})()

while 문을 이용하는 경우

// way09
const intializedArray = (() => {
  let arr = [];
  while (arr.push(Array(N).fill(init)) < M);
  return arr;
})()

성능 비교

JSBench에서 직접 코드를 작성하고 테스트를 돌려보았다.
각각 M*N의 경우가 100*100 이하 , 1,000*1,000 이상일 때로 산정하여 계산했다.

// small
const init = 0
const M = Math.floor(Math.random() * 100);
const N = Math.floor(Math.random() * 100);
// big
const init = 0
const M = Math.floor(Math.random() * (10000 - 1000) + 1000)
const N = Math.floor(Math.random() * (10000 - 1000) + 1000)
small(100*100 이하)big(1,000*1,000 이상)
way0116만 ops/s ± 50.19%5.9 ops/s ± 30.85%
way0215만 ops/s ± 44.69%8.5 ops/s ± 53.43%
way0312만 ops/s ± 24.7%6.4 ops/s ± 40.54%
way0416만 ops/s ± 32.11%8.5 ops/s ± 46.12%
way0518만 ops/s ± 55.63%4.6 ops/s ± 43.72%
way0620만 ops/s ± 60.87%3.8 ops/s ± 54.27%
way0713만 ops/s ± 45.76%7.2 ops/s ± 48.07%
way0812만 ops/s ± 27.8%7.5 ops/s ± 42.52%
way0914만 ops/s ± 33.06%6.1 ops/s ± 52.78%

small(100*100 이하)big(1,000*1,000 이상)
1위way06way02
2위way05way04
3위way04way08
4위way01way07
5위way02way03
6위way09way09
7위way07way01
8위way03way05
9위way08way06

(결과 참고-small)
(결과 참고-big)

흥미로운 결과다... M과 N의 크기에 따라서 결과가 확연히 차이가 났고,
그 중 제일인 것은 바로 이중 for 문인 way06이다.

그리고 각각의 주요 메서드에 따라서도 비교할 수 있는데,
from의 경우 {length: N}-(way03)로 empty하게 넣는 것보다 Array(N)-(way04)를 넣는 것이 항상 더 빨랐다.

그리고 for문의 경우 수치가 작을 경우 이중 for 문-(way06) - []로 초기화 뒤 fill-(way07) - Array(N)으로 초기화 뒤 fill-(way08) 순이었다가, 수치가 커질 경우 반대의 결과를 내놓았다.

코딩테스트를 친다고 가정할 때 결론을 내보자면 다음과 같다.

데이터 수치가 1만(100*100)이 넘어가지 않을 때,

  • 가장 빠른 결과를 내놓고 싶다? 👉 이중 for 문-(way06)
  • 근데 한 줄에 끝내고 싶다? 👉 spread 후 map으로 fill-(way05)

데이터 수치가 100만(1000*1000)이 넘어갈 때,

  • 가장 빠른 결과를 내놓고 싶다? 👉 new Array fill + new Array fill-(way02)

언제든지 무난하게 한 줄에, 빠르게 하고 싶다?

  • 👉 from에서 Array(N)으로 초기화 후 fill-(way03)

개인적으로 한 줄에 끝내고 싶은 마음이 크니깐, 가장 마지막 결론으로 앞으로 초기화를 애용하지 않을까 싶다!

참고

profile
Chaejung
프론트엔드 기술 학습 및 공유를 활발하게 하기 위해 노력합니다.
이전 포스트

[프로그래머스] 배열 관련 문제들(feat. 결과 통계 계산기)

다음 포스트

[프로그래머스] 가장 큰 수

0개의 댓글