[2018 카카오 블라인드 공채] 프렌즈4블록 (C++)

2018 카카오 블라인드 공채 1차 코테 문제

5시간을 잡고 실전처럼 진행하였으며 코드의 최적화나 알고리즘은 정확하지 않음.

---

코딩테스트 연습 - [1차] 프렌즈4블록 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - [1차] 프렌즈4블록

 

---

4번 문제였으며 약 1시간정도 소요되었음.

내리는 문자열 처리가 쉽지 않을꺼라 생각하여 오른쪽으로 90도 회전하고 삭제되면 왼쪽으로 미는형태로 풀기로 하였다.

그렇게 되면 삭제되는 블록은 string의 erase로 쉽게 처리할 수 있을꺼라 생각했다.

블록이 중복으로 제거되는것을 허용하였기 때문에 바로 지우지 않고 visited로 체크만 해주었다.

모든 블럭을 확인한 후, visited가 true인것의 수를 세고, true면 블록을 지워주었다.

다시보면 매개변수로 m, n이 들어오는데 일반적이지 않고 90도 회전하라고 힌트를 주는것 같다.

#include <string>
#include <vector>

using namespace std;

bool deleted[30][30] = { false };
int row, col;
vector<string> board;

int FIND_DELETE_NUM()
{
    bool visited[30][30] = { false };
    int num = 0;

    for (int i = 0; i < row - 1; i++)
    {
        if (board[i].size() < 2 || board[i + 1].size() < 2)
            continue;

        for (int j = 0; j < board[i].size() - 1; j++)
        {
            char temp = board[i][j];

            if ((temp == board[i + 1][j]) && (temp == board[i][j + 1]) && (temp == board[i + 1][j + 1]))
            {
                visited[i][j] = true;
                visited[i + 1][j] = true;
                visited[i][j + 1] = true;
                visited[i + 1][j + 1] = true;
            }
        }
    }

    for (int i = 0; i < row; i++)
    {
        int ind = 0;
        for (int j = 0; j < board.size(); j++)
        {
            if (visited[i][j])
            {
                board[i].erase(board[i].begin() + j - ind);
                num++;
                ind++;
            }
        }
    }

    return num;
}

int solution(int m, int n, vector<string> s) {
    int answer = 0;

    for (int i = 0; i < n; i++)
    {
        string temp = "";
        for (int j = m - 1; j >= 0; j--)
            temp += s[j][i];
        board.push_back(temp);
    }
    row = n; col = m;
    while (1)
    {
        int deleted_num = FIND_DELETE_NUM();
        if (deleted_num == 0)
            break;
        else
            answer += deleted_num;
    }
    return answer;
}