카카오 신입 공채 1차 코딩 테스트 문제 6. 프렌즈4블록(난이도: 상)

카카오 블라인드 채용에 출제된 문제가 공개돼 풀어보았다. 한 문제당 하나의 클래스로 만들었으며 테스트 코드까지 한꺼번에 올린다. 실제 채용 시험의 채점이 어떻게 이뤄졌는지 모르지만, 문제에 나와있는 입출력은 모두 만족하는 코드이다. 강의할 때도 늘 말하는 것이지만, 코드에 정답은 없다. 문제를 푸는 하나의 방법이 될 수 있음을 기억하고 참고하라.

문제 6. 프렌즈4블록(난이도: 상)

문제 설명과 해설은 아래 링크를 참고하라.

http://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/

개인적으론 6번이 5번 문제보다 쉽다고 보이는데, 난이도는 5번이 중 6번이 상이다.

import org.junit.Test;
 
import static org.junit.Assert.assertEquals;
 
public class Q6 {
    public static void main(String[] args) {
    }
 
    @Test
    public void question6_TC1() {
        int m = 4;
        int n = 5;
        String[] board = new String[]{"CCBDE", "AAADE", "AAABF", "CCBBF"};
 
        assertEquals(14, question6(m, n, board));
    }
 
    @Test
    public void question6_TC2() {
        int m = 6;
        int n = 6;
        String[] board = new String[]{"TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"};
 
        assertEquals(15, question6(m, n, board));
    }
 
    public int question6(int m, int n, String[] board) {
        char[][] backBoard = new char[m][n];
 
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                backBoard[i][j] = board[i].charAt(j);
            }
        }
 
        int totalNumRemoved = 0;
        int tempNumRemoved = 0;
        boolean isDone = true;
 
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(backBoard[i][j]);
            }
            System.out.println();
        }
 
        while (isDone) {
            tempNumRemoved = findAndRemove44Blocks(m, n, backBoard);
            totalNumRemoved += tempNumRemoved;
            if (tempNumRemoved == 0)
                isDone = false;
 
            System.out.println();
            System.out.println();
            System.out.println();
        }
 
        return totalNumRemoved;
 
    }
 
    private int findAndRemove44Blocks(int m, int n, char[][] backBoard) {
        int numRemoved = 0;
        //find
        boolean[][] toRemove = new boolean[m][n];
 
        for (int i = 0; i < m - 1; i++) {
            for (int j = 0; j < n - 1; j++) {
                //i, j+1
                //i+1, j+1
                //i+1, j
                if (backBoard[i][j] != ' ') {
                    if (backBoard[i][j] == backBoard[i][j + 1] &&
                            backBoard[i][j] == backBoard[i + 1][j + 1] &&
                            backBoard[i][j] == backBoard[i + 1][j]) {
                        toRemove[i][j] = true;
                        toRemove[i][j + 1] = true;
                        toRemove[i + 1][j + 1] = true;
                        toRemove[i + 1][j] = true;
                    }
                }
            }
        }
 
        //remove
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (toRemove[i][j]) {
                    backBoard[i][j] = ' ';
                    numRemoved++;
                }
            }
        }
 
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(backBoard[i][j]);
            }
            System.out.println();
        }
 
        while (true) {
            boolean isMoved = false;
            for (int i = m-1; i > 0; i--) {
                for (int j = 0; j < n; j++) {
                    if (backBoard[i][j] == ' ' && backBoard[i - 1][j] != ' ') {
                        backBoard[i][j] = backBoard[i - 1][j];
                        backBoard[i - 1][j] = ' ';
                        isMoved = true;
                    }
                }
            }
            if (isMoved == false) break;
        }
 
 
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(backBoard[i][j]);
            }
            System.out.println();
        }
 
        return numRemoved;
    }
}