2019 카카오 신입 공채 1차 코딩 테스트 풀이 - 7번문제

2018-12-02 17:03:56 | 조회수 3044



드디어 1차 마지막 문제입니다. 2차도 벌써 공개가 됐는데, 빠르게 빠르게 포스팅을 해야 할 것 같네요.


이번 문제는 제한된 테트리스 블록(3개) 가 놓여있는 필드에서, 검은 블록을 위에서 아래로 떨어뜨려 블록이 속이 꽉찬 직사각형을 만들 수 있으면 제거할 수 있다고 할 때, 최대 몇개의 블록이 제거되는지를 묻는 문제입니다. 이 문제는 구현 자체는 오히려 6번보다 쉬웠던 것 같습니다. 이 문제를 풀어보겠습니다.


문제를 풀기 위해선 먼저 각 블록들의 위치 정보를 맵핑해 놓는 방법으로 접근합니다. 사각형이 되었는지를 체크하기 위함인데, 간단한 방법이 있습니다. 배열을 선언하고, 해당 블록이 나타날 때마다 x좌표와 y좌표의 최소와 최댓값을 각각 저장해 놓는 것입니다.

class Tetris {

public:

    int sx, sy, ex, ey;

    //이하 생략

}

그다음 sx에는 블록이 나타났던 x좌표중 가장 작은 값, ex에는 가장 큰 값을 저장하게 하면 이후에 사각형이 되었는지 검사를 할 때, sx~ex, sy~ey 가 채워졌는지만 검사하면 됩니다.


다음은 블록을 채우는 방법인데요. 전형적인 시뮬레이션으로 채워볼 수 있습니다. 검은 블록의 개수가 제한되어 있지 않기 때문에, 맨 위에서부터 블록을 채울 수 있을 때까지 블록을 쭉 채워보는 겁니다. 저 같은 경우는 검은 블록을 -1로 했고, 제대로 채워지는지 출력을 해보며 테스트 했습니다.




이렇게까지 전처리를 해놓으면, 위에 말했던 것처럼 블록이 채워졌는지 검사를 하여 채워진 블록을 다시 0으로 돌려놓고, 정답을 1 증가시키면 됩니다. 없어지는 블록이 없을 때까지 반복하고, 결과를 출력하면 됩니다. 시간복잡도는 $O(n^2)$ 입니다. 상수가 약간 붙어 조금 더 소요될 수 있지만, 맵의 크기가 50 * 50 이므로 무시할 수 있습니다.


전체 소스는 하단의 소스코드를 클릭하면 볼 수 있습니다.


※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.

#include <string>
#include <algorithm>
#include <vector>
using namespace std;
class Tetris {
public:
    int sx, sy, ex, ey;
    bool init, clear;
    Tetris() { 
        sx = sy = 2e9;
        ex = ey = init = clear = 0;    
    }
} tetris[222];
int getrow(vector<vector<int>> &board, int col) {
    for (int i = 0; i < board.size(); i++) {
        if (board[i][col]) return i;
    }
    return board.size();
}
int solution(vector<vector<int>> board) {
    int cnt = 0, answer = 0;
    for (int i = 0; i < board.size(); i++)
        for (int j = 0; j < board[i].size(); j++)
            if (board[i][j]) {
                int idx = board[i][j];
                cnt = max(cnt, idx);
                tetris[idx].init = true;
                tetris[idx].sx = min(tetris[idx].sx, i);
                tetris[idx].ex = max(tetris[idx].ex, i);
                tetris[idx].sy = min(tetris[idx].sy, j);
                tetris[idx].ey = max(tetris[idx].ey, j);
            }
    bool change = false;
    while (1) {
        for (int i = 0; i < board.size(); i++) {
            int j = getrow(board, i);
            for(int k=0; k<j; k++) board[k][i] = -1;
        }
        for (int i = 1; i <= cnt; i++) {
            if (!tetris[i].init || tetris[i].clear) continue;
            bool f = true;
            for (int x = tetris[i].sx; x <= tetris[i].ex && f; x++)
                for (int y = tetris[i].sy; y <= tetris[i].ey && f; y++)
                    if (board[x][y] != i && board[x][y] != -1) f = false;
            if (f) {
                change = true;
                tetris[i].clear = true;
                answer++;
                for (int x = tetris[i].sx; x <= tetris[i].ex; x++)
                    for (int y = tetris[i].sy; y <= tetris[i].ey; y++)
                        board[x][y] = 0;
            }
        }
        if (!change) break;
        change = false;
        for (int i = 0; i < board.size(); i++)
            for (int j = 0; j < board.size(); j++)
                if(board[i][j] == -1) board[i][j] = 0;
    }
    return answer;
}


2019 카카오 신입 공채 1차 코딩 테스트 풀이 - 7번문제 - 알고리즘닷컴
32 개의 글