구현

프로그래머스 2018 KAKAO BLIND RECRUITMENT Level 2 문제 프렌즈 4블록을 Java를 이용해 풀어보았다.
스택을 이용했다.

문제 링크 첨부한다.
https://programmers.co.kr/learn/courses/30/lessons/17679

2x2 단위로 확인하기

현재 칸과 동쪽, 남쪽 그리고 동남쪽 칸까지 총 4칸이 모두 동일하면 visited 배열의 값을 true로 바꿔주며 (m-2,n-2)칸까지 확인한 후에 마지막에 모든 칸을 돌며 visited 값이 true인 곳은 '0'으로 바꿔주는 작업을 했다.
그림으로 표현하면 다음과 같다.
또한 지워주는 작업을 했으면 떨구는 작업도 해야하는데, 떨구는 작업을 해야할지 말아야할지 판별해주기 위해 return 값을 boolean으로 줬다.
이를 코드로 표현하면 다음과 같다.

Boolean checkAndDelete(int row, int col){
        boolean[][] visited = new boolean[row][col];
        boolean flag = false;

        for(int r=0; r<row-1; r++){
            for(int c=0; c<col-1; c++){
                char prev = boardAry[r][c];
                if(prev=='0')   continue; // 만약 빈 곳이면 넘겨
                int check = 0;

                for(int dir=0; dir<3; dir++){ // 나머지 세 칸 확인
                    char next = boardAry[r+move[dir][0]][c+move[dir][1]];
                    if(next=='0')   break;
                    if(prev!=next)  break;
                    check++;
                }
                if(check==3){ // 만약 네 칸 모두 동일한 모양이면 방문 정보 갱신
                    flag = true; // fallDown 실행해야 할지 결정해줄 변수
                    visited[r][c] = true;
                    for(int dir=0; dir<3; dir++)
                        visited[r+move[dir][0]][c+move[dir][1]] = true;
                }
            }
        }

        for(int r=0; r<row; r++)
            for(int c=0; c<col; c++)
                if(visited[r][c]) {
                    boardAry[r][c] = '0';
                    cnt++;
                }

        return flag;
    }

이렇게 지우는 작업을 마쳤으면 떨구는 작업을 이어서 해줘야 한다.

떨어뜨리기

떨어뜨리는 작업은 하나의 column씩 검사하며 아래에서 위로 올라가며 비어있지 않은 것들만 추가해준 후에, 위에서부터 알맞은 위치에서 pop()을 해줘서 채우면 된다. 비어있어야 할 칸에는 '0'을 채워준다.

void fallDown(int row, int col){ // 삭제 후 떨구는 메소드
        Stack<Character> stack = new Stack<>();

        for(int c=0; c<col; c++){
            for(int r=row-1; r>=0; r--){
                if(boardAry[r][c]!='0') stack.add(boardAry[r][c]);
            }
            for(int r=0; r<row; r++){
                if(r<row-stack.size())  boardAry[r][c] = '0';
                else boardAry[r][c] = stack.pop();
            }
        }
    }

지우는 작업과 떨구는 작업은 다음과 같이 표현할 수 있다.

while(checkAndDelete(m,n))
      fallDown(m,n);

String[] -> char[][]

앞서 살펴본 작업들에서는 입력값으로 들어온 String[]이 아닌 char[][]을 다루는 것을 확인할 수 있다. 이건 미리 작업해둔 거다.

static char[][] boardAry = new char[m][n];

for(int i=0; i<m; i++)
    boardAry[i] = board[i].toCharArray();

위의 모든 코드들을 합치면 다음과 같다. 내가 제출한 코드다.

import java.util.Stack;

public class Friends4Block {
    static int[][] move = { {0,1}, {1,0}, {1,1} }; // 자신,동,남,남동
    static char[][] boardAry;
    static int cnt = 0;

    static int solution(int m, int n, String[] board) {
        boardAry = new char[m][n];
        for(int i=0; i<m; i++)
            boardAry[i] = board[i].toCharArray();

        while(checkAndDelete(m,n))
            fallDown(m,n);

        int answer = cnt;
        return answer;
    }

    static Boolean checkAndDelete(int row, int col){
        boolean[][] visited = new boolean[row][col];
        boolean flag = false;

        for(int r=0; r<row-1; r++){
            for(int c=0; c<col-1; c++){
                char prev = boardAry[r][c];
                if(prev=='0')   continue; // 만약 빈 곳이면 넘겨
                int check = 0;

                for(int dir=0; dir<3; dir++){ // 나머지 세 칸 확인
                    char next = boardAry[r+move[dir][0]][c+move[dir][1]];
                    if(next=='0')   break;
                    if(prev!=next)  break;
                    check++;
                }
                if(check==3){ // 만약 네 칸 모두 동일한 모양이면 방문 정보 갱신
                    flag = true; // fallDown 실행해야 할지 결정해줄 변수
                    visited[r][c] = true;
                    for(int dir=0; dir<3; dir++)
                        visited[r+move[dir][0]][c+move[dir][1]] = true;
                }
            }
        }

        for(int r=0; r<row; r++)
            for(int c=0; c<col; c++)
                if(visited[r][c]) {
                    boardAry[r][c] = '0';
                    cnt++;
                }

        return flag;
    }

    static void fallDown(int row, int col){ // 삭제 후 떨구는 메소드
        Stack<Character> stack = new Stack<>();

        for(int c=0; c<col; c++){
            for(int r=row-1; r>=0; r--){
                if(boardAry[r][c]!='0') stack.add(boardAry[r][c]);
            }
            for(int r=0; r<row; r++){
                if(r<row-stack.size())  boardAry[r][c] = '0';
                else boardAry[r][c] = stack.pop();
            }
        }
    }

    public static void main(String[] args) {
        int m = 6;
        int n = 6;
        String[] board = { "TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ" };
        int answer = solution(m,n,board);
        System.out.println(answer);
    }
}