[문제풀이 후기] 프로그래머스 #120866 - 안전지대

https://school.programmers.co.kr/learn/courses/30/lessons/120866

 

기본 상위 코드

const board = [
  [0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0],
  [0, 0, 1, 1, 0],
  [0, 0, 0, 0, 0],
];

 

첫 번째 시도 (결과 : 성공)

 

접근 방식

1. 별도의 배열 생성
2. 위험 지역의 칸을 생성하는 함수 구현
3. 1 이 있는 칸 탐색 후 발견 시 위험 지역 칸 추가
4. 최종적으로 0 인 칸 개수 반환

const [rowLength, colLength] = [board.length, board[0].length];

// 결과 배열
const resultBoard = Array.from({ length: rowLength }, () =>
  Array.from({ length: colLength }, () => 0),
);

// 위험 지역 칸 생성 함수
const drawDangerZone = (r, c, board) => {
  // row - 1
  if (r > 0 && c > 0) board[r - 1][c - 1]++;
  if (r > 0) board[r - 1][c]++;
  if (r > 0 && c < colLength - 1) board[r - 1][c + 1]++;

  // row
  if (c > 0) board[r][c - 1]++;
  board[r][c]++;
  if (c < colLength - 1) board[r][c + 1]++;

  // row + 1
  if (r < rowLength - 1 && c > 0) board[r + 1][c - 1]++;
  if (r < rowLength - 1) board[r + 1][c]++;
  if (r < rowLength - 1 && c < colLength - 1) board[r + 1][c + 1]++;
};

// 1 이 있는 칸 탐색 후 위험 지역 칸 추가
for (let r = 0; r < rowLength; r++) {
  for (let c = 0; c < colLength; c++) {
    if (board[r][c] === 1) {
      drawDangerZone(r, c, resultBoard);
    }
  }
}

return resultBoard.flat().filter((value) => value === 0).length;

---

 

두 번째 시도 (결과 : 성공)

 

접근 방식

1. 주변 8칸의 좌표 배열 사용
2. 각 칸마다 주변 8칸의 좌표 탐색 후 안전한 칸 개수++

// 주변 8칸 좌표 배열
const outsideArray = [
  [-1, -1],
  [-1, 0],
  [-1, 1],
  [0, -1],
  [0, 1],
  [1, -1],
  [1, 0],
  [1, 1],
];

let safeZoneCount = 0; // 안전 지역 칸 개수

// 각 칸마다 주변 8칸 좌표 탐색 후 안전 지역 칸 개수++
board.forEach((row, y, self) =>
  row.forEach((value, x) => {
    if (value === 1) return false;
    return outsideArray.some(([outY, outX]) => !!self[outY + y]?.[outX + x])
      ? false
      : safeZoneCount++;
  }),
);

return safeZoneCount;

---

세 번째 시도 (결과 : 성공)

 

접근 방식

1. 1 인 칸 탐색
2. 주변 탐색 후 0 -> 2 로 변경

for (let r = 0; r < board.length; r++) {
  for (let c = 0; c < board[0].length; c++) {
    if (board[r][c] === 1) {
      for (let i = -1; i <= 1; i++) {
        for (let j = -1; j <= 1; j++) {
          if (board[r + i]?.[c + j] === 0) board[r + i][c + j] = 2;
        }
      }
    }
  }
}

return board.flat().filter((value) => value === 0).length;

 

효과

메모리 : 33.5 MB -> 33.4 MB
시간 : 0.48 ms -> 0.27 ms

 

후기

흠.. 세 방법 모두 시간 복잡도는 O(n^2) 인데 왜 세번째가 시간이 제일 빠른걸까..