(Java) 프로그래머스 - 프렌즈4블록

꽤나 재밌어 보이는 문제여서 선택했지만 2단계 문제 치고 어렵다는 느낌이 들었다.

지금까지 풀어본 문제 중에 가장 구현 난이도가 높았던 것 같다.

그래서인지 이번에는 입력값을 n과 m을 30 이하, 블록은 A~Z 까지로 제한 시간을 넉넉하게 준 것 같다. 

입력값이 크지 않으니 실제 코드를 작성할 때도 우당탕 3중 for문까지 돌려가면서 풀었던 것 같다.

 

설계는 간단하지만 생각해야 할 포인트가 꽤 있다.

1. 제거할 블록은 한 번에 제거해야 한다.

2, 제거할 블록이 겹친다면 겹쳐지는 부분은 한 번만 카운팅 되어야 한다.

3. 블록을 아래로 떨어트리는 로직을 생각하는 것이 쉽지 않다.

 

내가 생각한 로직은

1. 제거할 블록의 좌표를 찾는다.

나는 3중 for문을 이용해서 모든 i, j값을 돌며 오른쪽, 아래, 대각선 좌표를 탐색하고 target의 좌표를 list에 넣었다.

그래야 겹치는 블록을 알 수 있고, 한 번에 제거하기 편하기 때문이다.

 

2. 블록을 실제로 제거한다.

list에 넣어둔 좌표를 이용해서 제거해야 할 블록을 빈 문자열로 만든다. 만약 while문을 반복하다가 더 이상 탐색할 좌표가 없으면 list가 비어있게 될 텐데 그러면 탐색을 중단하면 된다.

 

3. 제거된 블록의 빈자리로 위에 블록을 떨어트린다. 

가장 밑에 행, 가장 왼쪽 열부터 탐색을 시작하다가 빈 문자열을 만나면 바로 그 위 행, 같은 열로 이동하다 비어있지 않은 문자열을 만날 때까지 탐색한다. 비어있지 않은 문자열을 만나면 그 문자열을 처음 빈 문자열을 만난 부분에 저장하고 빈 문자열로 변경한다. 

 

---

최종 코드

import java.util.*;
class Solution {
    static int[] dx = {0, 1, 1};
    static int[] dy = {1, 0, 1};
    static List<int[]> list;
    static int answer;
    static boolean flag;
    public int solution(int m, int n, String[] board) {
        answer = 0;

        // 2차원 배열로 변경
        String[][] arr = new String[m][n];
        for (int i = 0; i < m; i++) {
            arr[i] = board[i].split("");
        }

        // 제거할 블록의 시작 좌표를 저장할 list
        list = new ArrayList<>();
        // while문을 종료하기 위한 boolean
        flag = false;

        // 더이상 제거할 블록이 없다면 탐색 중지
        while (!flag) {
            search(arr);
            remove(arr);
            pull(arr);
        }
        return answer;
    }
    // 제거할 블록의 좌표를 찾는 메서드
    static void search(String[][] arr) {
        // 2차원 배열의 모든 좌표를 탐색
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr[0].length - 1; j++) {
                // target 설정
                String target = arr[i][j];
                // 탐색할 블록이 "" 이면 탐색할 필요 없음
                if (target.equals("")) {
                    continue;
                }

                // 블록 4개가 모두 같은지 확인할 변수
                int cnt = 0;
                for (int k = 0; k < 3; k++) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];

                    // target 블록과 같다면 cnt 증가
                    if (target.equals(arr[nx][ny])) {
                        cnt++;
                    }
                    // 제거해야할 4개의 블록이 모이면 target 좌표 저장
                    if (cnt == 3) {
                        list.add(new int[]{i, j});
                    }
                }
            }
        }
    }

    // 블록 제거 메서드
    static void remove(String[][] arr) {
        for (int[] i : list) {
            int[] temp = i;
            // target의 블록 먼저 제거
            // 블록이 ""이 아니라면 빈칸으로 만들고 answer 증가
            if (!arr[temp[0]][temp[1]].equals("")) {
                arr[temp[0]][temp[1]] = "";
                answer++;
            }
            // 왼쪽, 아래, 대각선 블록 제거
            for (int j = 0; j < 3; j++) {
                int nx = temp[0] + dx[j];
                int ny = temp[1] + dy[j];
                if (!arr[nx][ny].equals("")) {
                    arr[nx][ny] = "";
                    answer++;
                }
            }
        }
        // 만약 제거해야할 블록이 없다면 flag 상태 변경
        if(list.isEmpty()) {
            flag = true;
        }

        // 다음 탐색을 위해서 list clear
        list.clear();
    }

    // 블록을 아래로 떨어트리는 메서드
    static void pull(String[][] arr) {
        // 가장 밑 행부터 탐색
        for (int i = arr.length - 1; i >= 0; i--) {
            for (int j = 0; j < arr[0].length; j++) {
                // 탐색하다 ""을 만나면 같은열의 이전 행의 값을 가져오기
                if (arr[i][j].equals("")) {
                    for (int k = i; k >= 0; k--) {
                        if (!arr[k][j].equals("")) {
                            arr[i][j] = arr[k][j];
                            arr[k][j] = "";
                            break;
                        }
                    }
                }
            }
        }
    }
}