[프로그래머스] [Level2] 프렌즈4블록 - JAVA

[문제]

• 프로그래머스 level2
• 2018 KAKAO BLIND RECRUITMENT 출제 

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

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

 

[풀이]

1. 블록의 처음 칸부터 순회하며 현재 칸을 포함한 2 × 2 영역을 확인한다. 

2. 모두 같은 문자이면 4칸 모두 checked=true 표시 

3. 모든 블록을 탐색한 후 checked=true로 표시된 곳은 지워준다. 그리고 지워진 영영만큼 위 블록을 아래로 내려준다. 
※ 나는 지워준다는 의미로 해당 칸의 문자를 "X"로 치환했다. 그런데 테스트케이스9번에서 실패가 떴다. 
라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C) <-- 이 문자들만 아니면 상관없다고 생각했는데 문자 대신 "-1" 을 넣으니 모두 성공함.(-_-);;; (버그인듯)

4. while문을 돌며 (1->2->3)을 반복 수행. 블록을 모두 탐색하는데 4칸 모두 같은 문자인 경우가 하나도 없으면 더 이상 지울 블록이 없다는 뜻이므로 while문 종료.

5. 블록에서 지워진 칸(-1)의 개수를 세서 return

[코드]

package com.algorithm.kakaoTest.two;

import java.util.Arrays;

/**
 * 2018 KAKAO BLIND RECRUITMENT
 * [1차] 프렌즈4블록
 * 소요시간: 1시간 28분
 */
public class Test01_2 {
    public static void main(String[] args) {
        int m = 4;
        int n = 5;
        String[] board = {"CCBDE", "AAADE", "AAABF", "CCBBF"};
        int answer = solution(m, n, board);
        System.out.println(answer);
    }

    public static String[][] boards;
    public static boolean[][] checked;
    public static final String EMPTY = "-1";
    public static int[] xArray = {0, 0, 1, 1};
    public static int[] yArray = {0, 1, 0, 1};

    public static int solution(int m, int n, String[] board) {
        int answer = 0;
        boards = new String[m][n];
        checked = new boolean[m][n];

        makeBoard(board); // 2차원 배열 블록 생성

        boolean flag = true;
        while (flag) {

            // 4블록 영역 체크 여부 초기화
            for (int i = 0; i < checked.length; i++) {
                Arrays.fill(checked[i], false);
            }

            flag = findFourSections(); // 4블록 영역들을 찾고 지워줌
            dropBlocks(); // 윗 블록들을 떨어뜨려 빈 영역을 채움
        }

        for (int i = 0; i < boards.length; i++) {
            for (int j = 0; j < boards[i].length; j++) {
                if (boards[i][j].equals(EMPTY)) {
                    answer++;
                }
            }
        }
        return answer;
    }

    public static void makeBoard(String[] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length(); j++) {
                boards[i][j] = board[i].charAt(j) + "";
            }
        }
    }

    public static boolean findFourSections() {
        boolean flag = false;
        for (int i = 0; i < boards.length - 1; i++) {
            for (int j = 0; j < boards[i].length - 1; j++) {
                if (!boards[i][j].equals(EMPTY)) { // 빈영역(앞서 4블록으로 체크되어 지워진 영역임)
                    if (isFourBlockSameCharacter(boards[i][j], i, j)) {
                        flag = true;
                        setChecked(i, j);
                    }
                }
            }
        }
        return flag;
    }

    public static boolean isFourBlockSameCharacter(String s, int x, int y) {
        for (int i = 0; i < 4; i++) {
            if (!boards[x + xArray[i]][y + yArray[i]].equals(s)) {
                return false;
            }
        }
        return true;
    }

    public static void setChecked(int x, int y) {
        for (int i = 0; i < 4; i++) {
            checked[x + xArray[i]][y + yArray[i]] = true;
        }
    }

    public static void dropBlocks() {
        for (int i = boards.length - 1; i >= 0; i--) {
            for (int j = 0; j < boards[i].length; j++) {
                if (checked[i][j]) {
                    boards[i][j] = EMPTY;
                    int index = i;
                    while (index >= 0 && checked[index][j]) {
                        index--;
                    }

                    if (index >= 0) {
                        boards[i][j] = boards[index][j];
                        checked[index][j] = true;
                    }
                }
            }
        }
    }
}