KAKAO 2018 BLIND RECRUITMENT의 구현 문제이다.
구현은 언제나 세세한 동작의 구현과 최적화가 어려운 것 같다.
먼저 내가 생각한 풀이는 아래와 같다.
- 가장 먼저, 참고용 Copy Board를 만들어 놓는다.
- Copy Board를 만드는 이유는, Board를 바꿔버리면 겹친 부분을 지울 수 없기 때문이다.
- A가 2 x 3으로 6개 겹쳐있다면, 2 x 2가 2개 겹쳐있으니 6개 모두 지워져야 한다.
- 하지만 내 풀이에서는 앞 2 x 2를 먼저 #으로 바꿔버리므로, 겹친 부분을 검사할 수 없다.
- Copy Board를 2 x 2로 모든 칸을 훑으며 검사한다.
- Copy Board의 2 x 2가 모두 같은 칸이라면, Board의 2 x 2를 #으로 바꾼다.
- 모두 훑었으면, 공중에 뜬 블럭을 아래로 내린다.
- Copy Board에 Board의 모습을 복사한다.
- 더 이상 바꿀 2 x 2가 없을 때 까지 위 과정을 반복한다.
예상대로 시간이 굉장히 많이 걸리는 코드였다.
통과는 했지만, 다른 사람의 최적화 된 풀이들을 좀 더 볼 필요가 있겠다.
내 풀이
#include <string>
#include <vector>
using namespace std;
bool no_pop = true; // 더 이상 pop할게 없는가?
void init_map(vector<string>& copy_board, vector<string> board) {
copy_board = board;
}
void can_pop(int st_x, int st_y, vector<string> copy_board, vector<string>& board) {
char stand = copy_board[st_x][st_y];
if (stand == '#') return;
for (int i = st_x; i < st_x + 2; i++)
for (int j = st_y; j < st_y + 2; j++)
if (stand != copy_board[i][j] || copy_board[i][j] == '#') return;
no_pop = false;
for (int i = st_x; i < st_x + 2; i++)
for (int j = st_y; j < st_y + 2; j++)
board[i][j] = '#';
}
void pull_down(vector<string>& board) {
int iter = 0;
while (true) {
if (iter >= board[0].size()) break;
bool no_sharp = true; // 더 이상 내릴 게 없는가?
for (int i = board.size()-1; i > 0; i--) {
if (board[i][iter] == '#' && board[i - 1][iter] != '#') {
no_sharp = false;
for (int j = i - 1; j < board.size()-1; j++) {
if (board[j + 1][iter] != '#') break;
swap(board[j][iter], board[j+1][iter]);
}
}
}
if (board[0][iter] == '#' || no_sharp) iter++;
}
}
int count_blank(vector<string> board) {
int cnt = 0;
for (auto i : board) {
for (auto k : i)
if (k == '#') cnt++;
}
return cnt;
}
int solution(int m, int n, vector<string> board) {
int answer = 0;
vector<string> copy_board;
init_map(copy_board, board);
while (true) {
no_pop = true;
for (int i = 0; i < m - 1; i++)
for (int j = 0; j < n - 1; j++)
can_pop(i, j, copy_board, board);
pull_down(board);
copy_board = board;
if (no_pop) break;
}
answer = count_blank(board);
return answer;
}
최적화된 풀이: Stack
다른 사람의 풀이를 보다가 Stack을 이용한 풀이를 보았다.
세상에.. Stack을 이용하면 굳이 블록을 내리는 Logic을 쓸 필요가 없다.
#include <string>
#include <vector>
#include <stack>
using namespace std;
int solution(int m, int n, vector<string> board) {
int answer = 0;
bool b[m][n];
stack<char> s[n];
int count = 1;
while (count > 0) {
fill(&b[0][0], &b[m-1][n], 0);
count = 0;
for (int y=0; y<m-1; y++) {
for (int x=0; x<n-1; x++) {
if (board[y][x] != '.' &&
board[y][x] == board[y][x+1] &&
board[y][x] == board[y+1][x] &&
board[y][x] == board[y+1][x+1]) {
b[y][x] = 1;
b[y][x+1] = 1;
b[y+1][x] = 1;
b[y+1][x+1] = 1;
}
}
}
// 4면이 같으면 Truth Table을 모두 True로 만든다.
for (int x=0; x<n; x++) {
int y=0;
while(y < m) {
if (b[y][x] != 1) s[x].push(board[y][x]);
else count++;
board[y++][x] = '.';
}
// 남은 블럭을 stack에 쌓고 빈 공간은 Count를 올리며 .로 만들어준다.
while(!s[x].empty()) {
board[--y][x] = s[x].top();
s[x].pop();
}
// 원래 board에 stack으로 옮겨 쌓았던 블록들을 채워준다.
}
answer += count;
// 반복!
}
return answer;
}