카카오 신입공채 1차 코딩테스트 문제6 프렌즈블록 JAVA 예제

카카오톡 1차 코딩 테스트 문제6 프렌즈블록 JAVA 예제

카카오 신입공채 1차 코딩테스트 문제6 프렌즈블록 JAVA 예제

---

문제설명

블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 “프렌즈4블록”. 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.

만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다. 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다.

블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.

만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다.

위 초기 배치를 문자로 표시하면 아래와 같다.

TTTANT

RRFACC

RRRFCC

TRRRAA

TTMMMF

TMMTTJ

각 문자는 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C)을 의미한다

입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.

입력 형식

• 입력으로 판의 높이 m, 폭 n과 판의 배치 정보 board가 들어온다.
• 2 ≦ n, m ≦ 30
• board는 길이 n인 문자열 m개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.

출력 형식

입력으로 주어진 판 정보를 가지고 몇 개의 블록이 지워질지 출력하라.

입출력 예제

• 입출력 예제 1의 경우, 첫 번째에는 A 블록 6개가 지워지고, 두 번째에는 B 블록 4개와 C 블록 4개가 지워져, 모두 14개의 블록이 지워진다.

• 입출력 예제 2는 본문 설명에 있는 그림을 옮긴 것이다. 11개와 4개의 블록이 차례로 지워지며, 모두 15개의 블록이 지워진다.

문제 해설

게임 요구 사항을 구현해보는 문제입니다. 같은 모양의 카카오프렌즈 블록이 2x2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임인데요. 인접한 모든 블록이 사라지는 실제 게임들과 달리 계산을 쉽게 하기 위해 2x2로 제한하고, 사라진 블록 자리에는 새로운 블록이 채워지지 않습니다. 그럼에도 불구하고 인접한 블록을 모두 스캔해야 하는 문제라 짧지 않은 코드가 필요했을 것 같네요. 이번 시험에서 가장 긴 코드가 필요한 문제였습니다. 자바의 경우 무려 80라인이나 필요했네요. 블록 매트릭스를 생성하여 스캔하고 제거해 나가는 작업을 반복하면서 더 이상 제거되지 않을 때 사라진 블록 자리의 수를 계산하면 됩니다.

이 문제의 정답률은 48.01%입니다.

문제출처 : http://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/

JAVA 예제

---

이번 문제는 카카오측에서는 난이도 '상'으로 표시 했지만, 이전에 풀었던 버스탑승시간표 구하기, 뉴스클러스트링등의 문제가 저에게는 더 어렵게 느껴졌습니다. 아무래도 익숙치 않아서 더 어렵게 느껴졌는지 모르겠습니다. 여튼 이번 문제는 예전에 많이 하던 뿌요뿌요 게임과 동일한 알고리즘이기 때문에 쉽게 이해할 수 있었고 그만큼 구현하기도 쉬웠습니다.

다만 for문을 통한 이중for문 연산을 많이 해야하기 때문에 연산이 복잡해서 라인수가 꽤 많이 나왔습니다.

import java.util.ArrayList;
 
public class BlockGame {
 
    public static void main(String[] args) {
        System.out.println(getRemoveCount(4, 5, new String[]{"CCBDE", "AAADE", "AAABF", "CCBBF"}));
        System.out.println(getRemoveCount(6, 6, new String[]{"TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"}));
    }
 
    public static int getRemoveCount(int m, int n, String[] arr) {
        // 입력받은 String 배열을 2차원 ArrayList로 변환
        ArrayList<ArrayList<String>> board = new ArrayList<ArrayList<String>>();
        for(String str : arr) {
            ArrayList<String> innerList = new ArrayList<String>();
            for(char c : str.toCharArray()) {
                innerList.add(String.valueOf(c));
            }
            board.add(innerList);
        }
        
        int totalCnt = 0;
        int hitCnt = 0;
        print(board);
        // processHit에서 삭제처리하고 삭제카운트를 올림.
        while((hitCnt = processHit(board)) > 0) {
            totalCnt += hitCnt;
            print(board);
            // 빈칸을 탐색하여 위에 있는 요소를 아래로 당김
            arrange(board);
            print(board);
        }
        return totalCnt;
    }
    
    private static int processHit(ArrayList<ArrayList<String>> board) {
        int hitCnt = 0;
        char[][] delMarkBoard = new char[board.size()][board.get(0).size()];
        
        // 삭제되는 블럭 위치는 별도로 delMarkBoard에 체크
        for(int i = 0 ; i < board.size() ; i++) {
            for(int j = 0 ; j < board.get(i).size() ; j++) {
                String cur = board.get(i).get(j);
                // 빈블럭이 아닌 경우 삭제되는지 확인
                if(!cur.isEmpty()) {
                    // 현재 i, j 위치가 삭제 대상인지 확인
                    if(    (cur.equals(getValue(i-1, j-1, board)) && cur.equals(getValue(i-1, j, board)) && cur.equals(getValue(i, j-1, board)))
                        || (cur.equals(getValue(i-1, j, board)) && cur.equals(getValue(i-1, j+1, board)) && cur.equals(getValue(i, j+1, board)))
                        || (cur.equals(getValue(i, j-1, board)) && cur.equals(getValue(i+1, j-1, board)) && cur.equals(getValue(i+1, j, board)))
                        || (cur.equals(getValue(i, j+1, board)) && cur.equals(getValue(i+1, j+1, board)) && cur.equals(getValue(i+1, j, board)))) {
                        delMarkBoard[i][j] = 'D';
                        hitCnt++;
                    }
                }
            }
        }
        
        // delMarkBoard에 체크된 위치 값 일괄 삭제
        for(int i = 0 ; i < delMarkBoard.length ; i++) {
            for(int j = 0 ; j < delMarkBoard[i].length ; j++) {
                if(delMarkBoard[i][j]=='D') {
                    board.get(i).set(j, "");
                }
            }
        }
        return hitCnt;
    }
 
    private static void arrange(ArrayList<ArrayList<String>> board) {
        // 역z 방향으로 탐색 하여 공백을 만난 경우 위쪽으로 계속 이동하면 공백이 아닌 문자를 발견하면 내려버리기
        for(int i = board.size()-1 ; i >= 0 ; i--) {
            for(int j = board.get(i).size()-1 ; j >= 0 ; j--) {
                if(board.get(i).get(j).isEmpty()) {
                    // 위쪽 방향으로 탐색하며 공백아닌 문자를 발견한 경우 swap
                    for(int k=i; k >= 0; k--) {
                        if(!board.get(k).get(j).isEmpty()) {
                            board.get(i).set(j, board.get(k).get(j));
                            board.get(k).set(j, "");
                            break;
                        }
                    }
                }
            }
        }
    }
    
    private static String getValue(int i, int j, ArrayList<ArrayList<String>> board) {
        String retVal = "";
        try {
            retVal = board.get(i).get(j);
        } catch (IndexOutOfBoundsException e) {
            retVal = "";
        }
        return retVal;
    }
    
    private static void print(ArrayList<ArrayList<String>> board) {
        for(int i = 0 ; i < board.size() ; i++) {
            for(int j = 0 ; j < board.get(i).size() ; j++) {
                System.out.print((board.get(i).get(j).isEmpty() ? " " : board.get(i).get(j)) + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
    
}