2018 KAKAO BLIND RECRUITMENT > [1차] 프렌즈4블록

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

프로그래머스

 

 

- 나의 풀이

✅ 이차원 배열 ➡︎ gameBoard

 

✅ 지워질 블록에 true 표시할 이차원 배열 ➡︎ checkBoard

 

✅ 지워질 2*2 블록 위치 확인 ➡︎ 아래 4개의 블록 캐릭터가 같으면 지워야 함

• [i][j] 
• [i][j+1] 
• [i+1][j] 
• [i+1][j+1]

✅ 블록 지우기 ➡︎ *표시

 

✅ 블록 내리기

 

 - 나의 코드

class Solution {
    public int solution(int m, int n, String[] board) {
        int answer = 0;
        
        //이차원 배열 gameBoard
        String[][] gameBoard = new String[m][n];
        
        for(int i=0; i<m; i++) {
            gameBoard[i] = board[i].split("");
        }
        //System.out.println(gameBoard[m-1][n-1]);
        
        while(true) {
            //지울 블록 유무 flag
            boolean flag = false;
            boolean[][] checkBoard = new boolean[m][n];
            
            //지워질 2*2 블록 위치 확인 ~> [i][j] [i][j+1] [i+1][j] [i+1][j+1]
            for(int i=0; i<m-1; i++) {
                for(int j=0; j<n-1; j++) {
                    String character = gameBoard[i][j];
                    
                    //*면 이미 지워진 캐릭터
                    if(!character.equals("*")
                      && gameBoard[i][j+1].equals(character)
                      && gameBoard[i+1][j].equals(character)
                      && gameBoard[i+1][j+1].equals(character)) {
                        checkBoard[i][j] = true;
                        checkBoard[i][j+1] = true;
                        checkBoard[i+1][j] = true;
                        checkBoard[i+1][j+1] = true;
                        
                        flag = true;
                    }
                }
            }
        
            //지울 블록이 없으면 종료
            if(!flag) {
               break; 
            }
            
            //블록 지우기 ~> *표시
            for(int i=0; i<m; i++) {
                for(int j=0; j<n; j++) {
                    if(checkBoard[i][j]) {
                        gameBoard[i][j] = "*";
                        answer++;
                    }
                }
            }

            //블록 내리기 ~> (+2, +0)
            for(int j=0; j<n; j++) { //각 열에 대해
                for(int i=m-1; i>0; i--) { //아래에서부터 위로 탐색
                    if(gameBoard[i][j].equals("*")) {
                        for(int k=i-1; k>=0; k--) { //위쪽 블록을 찾아서
                            if(!gameBoard[k][j].equals("*")) { //블록이 있으면
                                gameBoard[i][j] = gameBoard[k][j]; //블록을 아래로 내리고
                                gameBoard[k][j] = "*"; //위쪽은 빈칸으로 설정
                                break;
                            }
                            
                        }

                    }
                }
            }
        }
        
        return answer;
    }
}

+

 

✅ 블록 내리기 ➡︎ 큐 사용

 

- 다른 풀이 방식

import java.util.*;

class Solution {
    public int solution(int m, int n, String[] board) {
        int answer = 0;
        
        while (true) {
            // 이번턴 터졌는지 안터졌는지 2차원배열
            boolean[][] toRemove = new boolean[m][n];
            // 한개라도 터졌는지
            boolean flag = false;
            
            //터진곳 true로 바꾸고 flag 바꿈
            for (int i = 0; i < m - 1; i++) {
                for (int j = 0; j < n - 1; j++) {
                    String current = board[i].substring(j, j + 1);
                    if (!current.equals(" ") &&
                        current.equals(board[i].substring(j + 1, j + 2)) &&
                        current.equals(board[i + 1].substring(j, j + 1)) &&
                        current.equals(board[i + 1].substring(j + 1, j + 2))) {
                        toRemove[i][j] = true;
                        toRemove[i][j + 1] = true;
                        toRemove[i + 1][j] = true;
                        toRemove[i + 1][j + 1] = true;
                        flag = true;
                    }
                }
            }
            
            // 2. If no matches, break
            if (!flag) break;
            
            //하나의 열씩 확인
            for (int j = 0; j < n; j++) {
                Queue<String> queue = new LinkedList<>();

                // 끝에서 부터 true면 터진거라 answer++; 아니면 큐에 넣음
                for (int i = m - 1; i >= 0; i--) {
                    if (!toRemove[i][j]) {
                        queue.add(board[i].substring(j, j + 1));
                    } else { // 터진곳
                        answer++;
                    }
                }

                //큐를 다시 배열에 넣음 (행씩)
                for (int i = m - 1; i >= 0; i--) {
                    if (!queue.isEmpty()) {
                        board[i] = board[i].substring(0, j) + queue.poll() + board[i].substring(j + 1);
                    } else {
                        board[i] = board[i].substring(0, j) + " " + board[i].substring(j + 1);
                    }
                }
            }
        }
        
        return answer;
    }
}