카카오 코딩테스트 - 프렌즈 4블록

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

카카오 신입 공채 1차 코딩 테스트 문제 해설

예전에 비슷한 문제를 구현해본 적이 있어서, 그렇게 어렵지 않았지만 만약 처음 했다면 시간좀 잡아먹었을 것 같았다.

문제 자체는 이해하기 쉽다. 예전에 뿌요뿌요 게임을 생각하면 되는데, 현재 블럭상태에서 없앨 수 있는 블럭개수를 출력하면 된다(여기서 블럭 개수는 현재 블럭이 없어지고, 그 위에 있던 블럭들이 내려오고...이런 연쇄과정에서 총 없앨 수 있는 블럭의 개수이다)

 

문제 해결 과정은

1. 현재 상태에서 없앨 수 있는 블럭이 있는지(2x2 블럭이 있는지) 검사한다.

2. 있으면, 2x2블럭의 시작점(좌측상단)을 list에 저장한다.

3. 블럭을 없앤다

           3-1 없애는 방법은 시작점 좌표에서 (1,0), (1,1), (0,1)를 더한 위치에 있는 원소들을 공백으로 체크한다.  

           3-2 블럭의 제일 아래부터, 공백이 아닌 원소들을 아래로 아래로 떨군다. 중간에 공백이 있다면 떨어지고 그렇지 않으면 안떨어진다.

// https://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/
// 프렌즈 4블럭

import java.util.*;

class Solution {

    // 오른쪽, 아래, 왼쪽
    static int[] dx = { 1, 1, 0 };
    static int[] dy = { 0, 1, 1 };

    static List<Integer> listX = new ArrayList<Integer>();
    static List<Integer> listY = new ArrayList<Integer>();

    static char[][] blocks;
    static int count = 0;

    public int solution(int m, int n, String[] board) {

        int height = m;
        int width = n;
        blocks = new char[height][width];

        for (int i = 0; i < height; i++) {
            String str = board[i];
            for (int j = 0; j < width; j++) {
                blocks[i][j] = str.charAt(j);
            }
        }

        while (findRemovableBlocksAndCheck()) { // 제거할 수 있는 블럭이 발견할 떄까지, 그 블록들을 없애면서 반복
            removeBlocks();
        }

        return count;
    }

    boolean findRemovableBlocksAndCheck() { // 2x2구역이 있는지 검사,있다면 2x2구역의 시작점(왼쪽위)를 저장

        int height = blocks.length;
        int width = blocks[0].length;
        String str = "";

        for (int y = 0; y < height - 1; y++) { // 블럭이 만들어 지는 경우를 찾음, 찾으면 시작은(왼쪽위)를 저장
            for (int x = 0; x < width - 1; x++) {

                char c = blocks[y][x];
                if (c == ' ') { // '#'는 블럭의 시작점이 될 수 없기 때문에 continue;
                    continue;
                }
                int count = 0;
                int nx = 0, ny = 0;

                for (int k = 0; k < 3; k++) { // 오른쪽/오른쪽+아래/아래 부분에서 현재 문자와 같은지 검사
                    ny = y + dy[k];
                    nx = x + dx[k];
                    if (blocks[ny][nx] == c) {
                        count++;
                    }
                }
                if (count == 3) { // 하나의 블럭을 찾으면 그 시작점을 리스트에 저장
                    listX.add(nx);
                    listY.add(ny - 1);
                }
            }
        }

        if (listX.size() > 0 && listY.size() > 0) { // 시작점이 있으면 return true;
            return true;
        }
        return false;
    }

    void removeAndDropBlocks() { // 없어질 블럭에 '#'를 표시하고, 남은 블럭을 재정렬

        int x, y;
        int height = blocks.length;
        int width = blocks[0].length;

        for (int i = 0; i < listX.size(); i++) { // 없앨 블럭을 표시

            y = listY.get(i);
            x = listX.get(i);

            if (blocks[y][x] != ' ') {
                blocks[y][x] = ' ';
                count++;
            }

            for (int k = 0; k < 3; k++) {
                int newY = y + dy[k];
                int newX = x + dx[k];
                if (blocks[newY][newX] != ' ') {
                    blocks[newY][newX] = ' ';
                    count++;
                }
            }
        }

        for (y = height - 1; y >= 0; y--) { // 블럭 재정렬
            for (x = 0; x < width; x++) {
                if (blocks[y][x] == ' ') {
                    continue;
                } else {
                    int yy = y;
                    while (yy + 1 < height && blocks[yy + 1][x] == ' ') {
                        char temp;
                        temp = blocks[yy][x];
                        blocks[yy][x] = blocks[yy + 1][x];
                        blocks[yy + 1][x] = temp;
                        yy++;

                    }
                }
            }
        }

        listX.clear();
        listY.clear();

    }
}

코드가 생각보다 좀 긴데, 실제로 알고보면 그렇게 어렵지 않다. 실제로 main함수에서 필요한 부분은 3줄이고, 나머지는 직접 작성한 함수이다. 함수는 총 findRemovableBlocksAndCheck(), removeAndDropBlocks()를 사용한다.

 

findRemovableBlocksAndCheck()는 제거할 수 있는 블럭이 있는지 확인하고, 있다면 그 좌표를 list에 저장한다.

removeAndDropBlocks()는 findRemovableBlocksAndCheck()가 true인 경우 실행되며 list에 저장된 좌표를 사용하여 블럭들을 없애고, 없앤 공간만큼 다시 재정렬한다.

 

findRemovableBlocksAndCheck()를 살펴보면,

1. 처음에 dfs를 사용하여 2x2블럭을 찾으려고 하였다. 하지만 크기가 고정되어있기 때문에 그렇게 할 필요는 없었다. 단순히 임의의 좌표(x,y)에서 오른쪽, 오른쪽아래,아래방향을 검사하면서 그 값들이 모두 같은지만 검사하면 된다. 또 마지막 행,렬은 어짜피 검사를 하지 않아도 되기 때문에 for문의 종료조건에 각각 -1을 해주었다. 

 

2. 각 방향이 같으면 count++를 해주고 마지막으로 count==3인 경우는 2x2블럭이 있음을 의미한다. 이런 경우, 2x2의 시작점(좌측상단)좌표를 리스트에 저장한다

 

 

removeAndDropBlocks()를 살펴보면,

이 함수는 두가지 역할을 한다. 따로 분리할 수 도 있었지만 둘 다 삭제하는 과정이기 때문에 합쳐놓았다.

 

1. 없앨 수 있는 블럭을 공백으로 체크한다. listX, listY에 없앨 수 있는 블럭의 시작점(좌측상단)의 좌표가 있기 때문에 그 위치를 기준으로 오른쪽, 오른쪽아래, 아래부분을 공백으로 모두 체크해준다. 이렇게 체크하면서 블럭을 하나씩 없애기 때문에 count(전역변수)값을 하나씩 증가해준다. 그리고 문제에서 2x3인 경우가 있는데 이런 경우는 2x2블럭 2개가 한쪽 부분만 겹쳐있는 경우이기 때문에 공백이 아닌 경우만 count++를 해주었다. 

 

2. 이렇게 모두 없앨 수 있는 블럭을 공백으로 체크했으면 이제 블럭을 재 정렬해주어여 한다. 이 부분은 y축 젤 아래부터 공백이 있는 만큼 블럭들을 내려주면 된다. 여기서는 y index를 0부터 아닌 height부터 시작했다. 그래야 논리적으로 아래로 당기는것이 말이 되기 때문이다. 일단 내려주는 부분은 공백이 아닌 원소들을 모두 내려주는데 조건은 y+1이 배열에 벗어나지 않고, y+1에 있는 원소가 공백일 때까지 반복한다. 이 과정에서 y+1와 y의 원소를 계속 바꾸어 준다(=아래로 계속 내린다). 다 끝났으면 list를 비워준다.