프로그래머스 - 프렌즈4블록 문제 (자바)

https://programmers.co.kr/learn/courses/30/lessons/17679

코딩테스트 연습 - [1차] 프렌즈4블록

 

모든 지점에서 아래, 오른쪽, 오른쪽 아래 3곳과 비교해서 전부 같으면 삭제하는 형태로 진행했습니다.

 

1. char 2차원 배열 -> int 2차원 배열

2. 모든 지점의 아래, 오른쪽, 오른쪽 아래 3곳 비교 후 처리

   - 우선 int 2차원 배열을 깊은 복사한다.

     (이유는 삭제 지점이 겹치는 경우 때문 비교에 사용하는 배열과 삭제를 반영하는 배열을 임시로 나누기 위함)

   - 지점별 3곳과 비교 후 전부 같으면 삭제 처리, 삭제 처리 과정에서 이미 삭제된 곳인 경우 count를 세지 않음

     (저 같은 경우 삭제를 -1로 하여 처리)

   - 깊은 복사한 배열로 초기화 및 count 반영

   - count가 1이상이면 삭제 된 경우로 재배치를 하고 삭제 과정을 진행해야함으로 boolean값을 리턴하게 함

3. 앞선 과정에서 삭제가 발생하면 재배치 과정을 진행

   - 2차원 배열의 오른쪽 아래 부터 삭제된 경우 자신의 위에 삭제 되지 않은 값과 값을 바꿈

 

ps 

2차원 배열은 clone 메서드, Arrays.copyOf 등으로 깊은 복사가 진행되지 않는다. 이유는 2차원 배열 내부에 int값이 있는게 아니라 int[] 객체이기 때문에 위의 메서드를 사용하더라고 객체를 참조하는 관계가 됨

2차원 배열 깊은 복사는 직접 진행해야함.

 

class Solution {
    // 아래, 오른쪽, 오른쪽 아래
    static int[] dx = {1, 0, 1};
    static int[] dy = {0, 1, 1};
    static int[][] matrix;
    static int answer;

    public int solution(int m, int n, String[] board) {
        matrix = new int[m][n];
        for(int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = board[i].charAt(j) - 'A';
            }
        }
        while (clear()) {
            move();
        }
        return answer;
    }

    static boolean clear() {
        int[][] temp = twoDimensionalArrayDeepCopy(matrix);
        int count = 0;

        for(int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                boolean isWillRemove = true;

                for (int k = 0; k < 3; k++) {
                    int tx = i + dx[k];
                    int ty = j + dy[k];

                    if (!isRanged(tx, ty) || matrix[i][j] != matrix[tx][ty]) {
                        isWillRemove = false;
                        break;
                    }
                }

                if (isWillRemove) {
                    if (!isAlreadyRemove(temp[i][j])) {
                        temp[i][j] = -1;
                        count++;
                    }

                    for (int k = 0; k < 3; k++){
                        int tx = i + dx[k];
                        int ty = j + dy[k];
                        if (!isAlreadyRemove(temp[tx][ty])) {
                            temp[tx][ty] = -1;
                            count++;
                        }
                    }
                }
            }
        }
        matrix = temp;
        answer += count;
        return count > 0;
    }

    static void move() {
        for (int i = matrix.length - 1; i >= 0; i--) {
            for (int j = matrix[i].length - 1; j >= 0; j--) {
                if (matrix[i][j] == -1) {
                    int x = i;
                    while (x > 0 && matrix[x][j] == -1) {
                        x--;
                    }
                    matrix[i][j] = matrix[x][j];
                    matrix[x][j] = -1;
                }
            }
        }
    }

    static int[][] twoDimensionalArrayDeepCopy(int[][] arr) {
        int[][] temp = new int[arr.length][arr[0].length];
        for (int i = 0; i < arr.length; i++) {
            for(int j = 0 ; j < arr[i].length; j++) {
                temp[i][j] = arr[i][j];
            }
        }
        return temp;
    }

    static boolean isAlreadyRemove(int val) {
        return val == -1;
    }

    static boolean isRanged(int x, int y) {
        return x >= 0 && x < matrix.length && y >= 0 && y < matrix[0].length;
    }
}