KAKAO 2018 BLIND RECRUITMENT의 구현 문제이다.
구현은 언제나 세세한 동작의 구현과 최적화가 어려운 것 같다.

먼저 내가 생각한 풀이는 아래와 같다.

  1. 가장 먼저, 참고용 Copy Board를 만들어 놓는다.
    • Copy Board를 만드는 이유는, Board를 바꿔버리면 겹친 부분을 지울 수 없기 때문이다.
    • A가 2 x 3으로 6개 겹쳐있다면, 2 x 2가 2개 겹쳐있으니 6개 모두 지워져야 한다.
    • 하지만 내 풀이에서는 앞 2 x 2를 먼저 #으로 바꿔버리므로, 겹친 부분을 검사할 수 없다.
  2. Copy Board를 2 x 2로 모든 칸을 훑으며 검사한다.
  3. Copy Board의 2 x 2가 모두 같은 칸이라면, Board의 2 x 2를 #으로 바꾼다.
  4. 모두 훑었으면, 공중에 뜬 블럭을 아래로 내린다.
  5. Copy Board에 Board의 모습을 복사한다.
  6. 더 이상 바꿀 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;
}