2019 카카오 신입 공채 1차 코딩 테스트 풀이 - 7번문제
-
유형
문제 요약
-
시뮬레이션, 구현문제 풀러 가기 : https://www.welcomekakao.com/learn/courses/30/lessons/42894
드디어 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;
}