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


작성일 : 2018-12-02 17:03:56
조회수 : 600



본문

드디어 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번문제 - 알고리즘닷컴
취업 대비 알고리즘에서는 다양한 기업들의 기출 문제 및 경향, 풀이 등에 대한 포스팅을 다룹니다.