[프로그래머스] [1차] 프렌즈4블록 (JAVA)

🗒️알고리즘 분류

#구현 #implementation

📌기억해야 할 포인트

전형적인 구현 문제이다.

• 블록을 없애는 상황만 유의해주면 된다.
  1. checkIf4BlocksAreSame(): 블록이 2×2 형태로 4개가 붙어있을 경우를 따로 2차원 배열(boolean[][] Check)를 만들어 체크해준다.
  2. removeBlocks(): 체크가 되어 있는 블럭들을 0 으로 만들어준다.
  3. down():없어진 부분을 제외하고 블록들을 중력이 작용하는 방향으로 내린다.
  4. initCheck(): 다시 Check 배열을 초기화 한다.
  5. if (nothingToRemove): 위의 과정을 제거된 블록들이 없을 때까지 반복한다.
• gravity(): 빈 배열(int[] tempArr)을 만들어서 기둥(column) 별로 0 이 아닌 부분만 빈 배열에 넣어주고, 그것을 다시 Board 배열에 넣어준다.

📝풀이 코드(JAVA)

class Solution {
    private int[][] Board;
    private boolean[][] Check;
    private boolean nothingToRemove = true;
    private int answer = 0, M = 0, N = 0;
    
    public int solution(int m, int n, String[] board) {
        M = m;
        N = n;
        Board = new int[M][N];
        Check = new boolean[M][N];
        
        initBoard(board);
        
        while (true) {
            nothingToRemove = true;
            
            checkIf4BlocksAreSame();
            removeBlocks();
            down();
            initCheck();
            
            if (nothingToRemove) {
                break;
            }
        }
        
        return answer;
    }
    
    private void checkIf4BlocksAreSame() {
        for (int i = 0; i < M-1; ++i) {
                for (int j = 0; j < N-1; ++j) {
                    if (Board[i][j] == 0) continue;
                    if (is4BlocksAreSame(i,j)) {
                        checkBlocks(i,j);
                    }
                }
            }
    }
    
    private void checkBlocks(int x, int y) {
        Check[x][y] = true;
        Check[x][y+1] = true;
        Check[x+1][y] = true;
        Check[x+1][y+1] = true;        
    }
    
    private void removeBlocks() {
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (Check[i][j]) {
                    Board[i][j] = 0;
                    nothingToRemove = false;
                    ++answer;
                }
            }
        }
    }
    
    private void down() {
        for (int col = 0; col < N; ++col) {
            gravity(col);
        }
    }
    
    private void gravity(int col) {
        int[] tempArr = new int[M];
        int endOfTempArr = M-1;
        
        for (int i = M-1; i >= 0; --i) {
            if (Board[i][col] != 0) {
                tempArr[endOfTempArr--] = Board[i][col];
            }
        }
        
        for (int i = M-1; i >= 0; --i) {
            Board[i][col] = tempArr[i];
        }
    }
    
    private void initCheck() {
        Check = new boolean[M][N];
    }
    
    private void initBoard(String[] board) {
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                char c = board[i].charAt(j);
                Board[i][j] = c-'A'+1;
            }
        }
    }
    
    private boolean is4BlocksAreSame(int x, int y) {
        return Board[x][y] == Board[x+1][y] && Board[x][y] == Board[x][y+1] && Board[x][y] == Board[x+1][y+1];
    }
}

⏰총 풀이시간

• 60분