카카오 블라인드 코딩 테스트 - 프렌즈4블록 풀이

코딩에 한시간 좀 넘은 듯 한데 생각보다 신입 코딩 테스트 치고는 난이도가 있는 문제인것 같다.

 

먼저 크게 검색->제거->이동(DropDown) 으로 행위를 나누었고, 2x2 동일한 블럭이 검색되지 않을때까지 매 라운드를 반복한다. 카카오에서 언급한 코드의 라인 수는 약 80~90라인인데 마지막에 리뷰하다 보니 다소 비효율적으로 짜여진 부분이 눈에 들어온다. 나중에 한번 시간나면 리팩터링도 해 봐야겠다.

 

1. 보드판 복사
   연산을 수행하고 결과를 만들 보드 객체를 별도로 생성(복제) 한다.
2. 2x2 동일 블럭 검색
   검색된 블럭의 위치를 삭제 예정 리스트에 넣는다.
3. 동일 블럭 삭제(' ' 대체)
   삭제 예정 리스트를 확인하며 블럭을 삭제한다. 검색과 삭제를 분리하지 않았을때 동시에 처리할 명확하고 간단한 방법이 문제 풀때 생각나지 않았으므로 따로 Task를 나누는 방식으로 해결했다.
4. 블럭 이동(DropDown)
   삭제된 블럭이 생기면 해당 위치를 상단에 있는 블럭이 채우도록 한다. (DropDown)
5. 2x2 동일한 블럭이 검색되지 않을떄까지 라운드를 계속 반복한다.

package net.albear.codingtest.programmers;

import java.util.*;

// https://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/
// 프렌즈4블록(난이도: 상)

public class FriendsBlock {
    public static void main(String[] args) throws Exception{
//        String[] board = new String[]{"CCBDE","AAADE","AAABF","CCBBF"};
        String[] board = new String[]{"TTTANT","RRFACC","RRRFCC","TRRRAA","TTMMMF","TMMTTJ"};
        new FriendsBlock().solution(board.length, board[0].length(), board);
    }

    public int solution(int m, int n, String[] board) {
        int answer = 0;

        // 1. 결과를 계산할 새로운 배열에 값을 복사한다.
        //    이떄 String 은 CharArray 형태로 변환하여 쉽게 탐색/수정 할 수 있도록 한다.
        List<char[]> newBoard = new ArrayList<>();
        for(String s: board){
            newBoard.add(s.toCharArray());
        }

        printBoardLayout("최초 원본", newBoard);

        // 전체 삭제된 블록 갯수
        int totalRemoveBlockCount = 0;
        // 하나의 Round에 삭제된 블록 갯수 (1라운드: 탐색->삭제->블록DropDown)
        int currentRemoveBlockCount;

        do {
            List<Integer[]> matchedBlockLocations = new ArrayList<>();
            for (int h = 0; h < newBoard.size(); h++) {
                for (int w = 0; w < newBoard.get(h).length; w++) {
                    // 2x2 계산 안되는건 pass
                    if (h > m - 2 || w > n - 2){
                        continue;
                    }
                    if (scanBlocksFromBoard(h, w, newBoard)) {
                        matchedBlockLocations.add(new Integer[]{h, w});
                    }
                }
            }

            // 블록 제거
            currentRemoveBlockCount = removeSameBlocksFromBoard(newBoard, matchedBlockLocations);

            // 삭제된 블록 print
            printBoardLayout("삭제후", newBoard);

            System.out.println("Current RemoveBlockCount > " + currentRemoveBlockCount);

            // 더이상 삭제할 블록이 없다면 종료.
            if (currentRemoveBlockCount == 0) break;

            // 블록 DropDown
            dropDownBlocksFromBoard(newBoard);

            // Drop 후 블록 print
            printBoardLayout("DropDown후", newBoard);

            // 삭제한 블록 갯수 업데이트
            totalRemoveBlockCount += currentRemoveBlockCount;
            System.out.println();
        }while(currentRemoveBlockCount > 0);

        System.out.println("Total RemoveBlockCount > " + totalRemoveBlockCount);

        return answer;
    }


    /**
     * 2x2 블록 검색
     *
     * @param h
     * @param w
     * @param newBoard
     * @return
     */
    private boolean scanBlocksFromBoard(int h, int w, List<char[]> newBoard){
        char n00 = newBoard.get(h)[w];
        char n01 = newBoard.get(h)[w+1];
        char n02 = newBoard.get(h+1)[w];
        char n03 = newBoard.get(h+1)[w+1];

        if(n00 == n01 && n01 == n02 && n02 == n03){
            return true;
        }else{
            return false;
        }
    }

    /**
     * Board에서 2x2 동일한 블럭을 삭제한다.
     *
     * @param board
     * @param matchedBlockLocations
     * @return
     */
    private int removeSameBlocksFromBoard(List<char[]> board, List<Integer[]> matchedBlockLocations){
        int removeCount = 0;

        for(Integer[] hwPoint : matchedBlockLocations){
            int h = hwPoint[0];
            int w = hwPoint[1];

            if(board.get(h)[w]     != ' '){ board.get(h)[w]      = ' '; removeCount++; }
            if(board.get(h)[w+1]   != ' '){ board.get(h)[w+1]    = ' '; removeCount++; }
            if(board.get(h+1)[w]   != ' '){ board.get(h+1)[w]    = ' '; removeCount++; }
            if(board.get(h+1)[w+1] != ' '){ board.get(h+1)[w+1]  = ' '; removeCount++; }
        }

        return removeCount;
    }

    /**
     * 아래가 비어있는 블록을 하단으로 이동한다.
     *
     * @param board
     */
    private void dropDownBlocksFromBoard(List<char[]> board){
        Queue<Integer> queue = new LinkedList<>();
        for(int w=board.get(0).length-1; w>=0; w--){
            for(int h=board.size()-1; h>=0; h--){
                char curBlock   = board.get(h)[w];

                if(curBlock == ' '){
                    queue.add(h);
                    continue;
                }else{
                    try{
                        // 이전에 빈블럭이 있었는지 확인해서 위치를 가져온다.
                        int emptyHeightIndex = queue.remove();

                        // 이번 빈블럭 위치에 현재 블럭을 넣고 현재 위치는 비워둔다.
                        board.get(emptyHeightIndex)[w] = curBlock;
                        board.get(h)[w] = ' ';

                        // 현재 위치가 이제 빈 블럭이므로 queue에 넣어준다.
                        queue.add(h);
                    }catch(NoSuchElementException e){ /* Exception 이 났다는건 하단에 빈블럭이 없다는 말이므로 옮길 필요가 없어 pass 한다. */ }
                }
            }
            queue.clear();
        }
    }

    /**
     * 입력받은 board 객체의 블록들을 출력한다.
     *
     * @param title
     * @param board
     */
    private void printBoardLayout(String title, List<char[]> board){
        System.out.println("===== "+title+" =====");
        for (int i = 0; i < board.size(); i++) {
            System.out.println(board.get(i));
        }
    }
}