내 풀이

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int solution(int[][] board) {

        int n = board.length;
        int answer = n * n;
        List<List<Integer>> dangerous = new ArrayList<>();

        // {좌상단, 상단, 우상단, 좌측, 우측, 좌하단, 하단, 우하단} 순서
        int[] dY = {-1, -1, -1,  0,  0,  1,  1,  1}; // row 변화량
        int[] dX = {-1,  0,  1, -1,  1, -1,  0,  1}; // column 변화량

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 지뢰를 발견하면
                if (board[i][j] == 1) {
                    // 8방향으로 확인
                    List<Integer> bomb = new ArrayList<>();
                    bomb.add(i);
                    bomb.add(j);
                    if (!dangerous.contains(bomb)) dangerous.add(bomb);

                    for (int k = 0; k < dY.length; k++) {
                        int y = i + dY[k];
                        int x = j + dX[k];
                        // y, x의 값이 board 안에 있는지 확인
                        boolean withInHeight = 0 <= y && y < n;
                        boolean withInWidth = 0 <= x && x < n;

                        // 범위를 벗어나면 pass
                        if (!(withInHeight && withInWidth)) continue;

                        // 범위 안에 들어갔지만 dangerous에 이미 있는 위험지역이라면 pass
                        List<Integer> area = new ArrayList<>();
                        area.add(y);
                        area.add(x);

                        if (dangerous.contains(area)) continue;

                        // dangerous 2차원 배열에 추가
                        dangerous.add(area);
                    }
                }
            }
        }

        return answer - dangerous.toArray().length;
    }
}

리팩토링(from 뤼튼)

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int solution(int[][] board) {
        int n = board.length;
        // 위험 지역을 표시할 2차원 배열 (0: 안전, 1: 위험)
        int[][] dangerousMap = new int[n][n]; 

        // {좌상단, 상단, 우상단, 좌측, 우측, 좌하단, 하단, 우하단} 순서
        int[] dY = {-1, -1, -1,  0,  0,  1,  1,  1}; // row 변화량
        int[] dX = {-1,  0,  1, -1,  1, -1,  0,  1}; // column 변화량

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 지뢰를 발견하면
                if (board[i][j] == 1) {
                    // 1. 지뢰가 있는 곳 자체도 위험 지역입니다.
                    dangerousMap[i][j] = 1;

                    // 2. 8방향 주변 지역도 위험 지역으로 표시합니다.
                    for (int k = 0; k < dY.length; k++) {
                        int y = i + dY[k];
                        int x = j + dX[k];
                        
                        // y, x의 값이 board 안에 있는지 확인
                        boolean withInHeight = 0 <= y && y < n;
                        boolean withInWidth = 0 <= x && x < n;

                        // 범위 안에 있다면 위험 지역으로 표시
                        if (withInHeight && withInWidth) {
                            dangerousMap[y][x] = 1;
                        }
                    }
                }
            }
        }

        int safeAreaCount = 0;
        // dangerousMap을 순회하며 안전 지역(0으로 표시된 곳)의 개수를 셉니다.
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dangerousMap[i][j] == 0) {
                    safeAreaCount++;
                }
            }
        }

        return safeAreaCount;
    }
}

성능 저하 원인

  1. contains() 메서드의 비효율성

: ArrayList의 contains() 메서드는 특정 요소가 리스트에 있는지 확인하기 위해

리스트의 처음부터 끝까지 모든 요소를 순회하며 비교해야 한다.

리스트의 크기가 D라고 할 때, contains() 연산은 평균적으로 O(D)의 시간 복잡도를 가진다.

  1. 객체 생성 오버헤드

List<List<Integer>> 안에 저장되는 List<Integer> 객체(좌표 하나당)들이 매번 생성되고,

그 과정에서 메모리 할당 및 해제와 같은 부가적인 비용이 발생한다.

  1. Auto-boxing/unboxing