ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 카카오 1차 온라인 코딩테스트 6번 문제(17.09.16)
    💻 프로그래밍/알고리즘 2017. 10. 16. 23:41

    안녕하세요! 개발하는 JAY입니다~ 오늘하루 즐거우셨나요?? 


    저는 요새 유일한 낙이 블로그 포스팅과 알고리즘 문제 푸는 겁니다:D 여러분들도 힘들고 많은 고민들 있으시겠지만, 


    그래도 우리 조금만 더 힘내서 더 좋은 개발자가 되봅시다!! 고생한 만큼 낙이 온다고도 하잖아요~^^


    자! 오늘은 6번문제를 한번 풀어보도록 하겠습니다.


    문제 및 풀이 링크 : http://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/


    6. 프렌즈4블록(난이도: 상)

    블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 “프렌즈4블록”.
    같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.

    만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다. 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다.

    블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.

    만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다.

    위 초기 배치를 문자로 표시하면 아래와 같다.

    TTTANT
    RRFACC
    RRRFCC
    TRRRAA
    TTMMMF
    TMMTTJ
    

    각 문자는 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C)을 의미한다

    입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.

    입력 형식

    • 입력으로 판의 높이 m, 폭 n과 판의 배치 정보 board가 들어온다.
    • 2 ≦ n, m ≦ 30
    • board는 길이 n인 문자열 m개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.

    출력 형식

    입력으로 주어진 판 정보를 가지고 몇 개의 블록이 지워질지 출력하라.

    입출력 예제

    mnboardanswer
    45[“CCBDE”, “AAADE”, “AAABF”, “CCBBF”]14
    66[“TTTANT”, “RRFACC”, “RRRFCC”, “TRRRAA”, “TTMMMF”, “TMMTTJ”]15

    예제에 대한 설명

    • 입출력 예제 1의 경우, 첫 번째에는 A 블록 6개가 지워지고, 두 번째에는 B 블록 4개와 C 블록 4개가 지워져, 모두 14개의 블록이 지워진다.
    • 입출력 예제 2는 본문 설명에 있는 그림을 옮긴 것이다. 11개와 4개의 블록이 차례로 지워지며, 모두 15개의 블록이 지워진다.

    문제풀이

    사실 이런 문제는 제가 아~~주 좋아하는 문제입니다. 고등학교때 LED 도트매트릭스, TFT-LCD를 가지고 테트리스랑 벽돌치기를 만들어본 적이 있는데요. 그때 이후로 이런 블럭 문제를 재밌어 했습니다.


    이 문제도 테트리스와 약간 유사한 면도 있죠? 블럭이 사라지면 아래로 떨어지는게 유사한 동작이군요.


    저는 아래와 같이 알고리즘을 짰습니다.


    1. 블럭을 순차적으로 돌면서 (x, y) (x, y +1), (x + 1, y), (x + 1, y + 1) 인접한 4개의 블럭이 같은 블럭인지 체크한다.

       (이때, 대문자일 경우 사라질 개수 증가)

    2. 같은블럭일 경우 소문자로 만들어 사라질 블럭이라는 걸 체크해준다.(A->a)

       (단, 1번에서 비교할때, A = a 이다. 이유는 교차해서 4개의 블럭을 체크할 수 있기 때문이다.)



    (이런 경우 가운데 라이언은 두번 체크가 가능해야함)


    3. 모든 블럭을 체크한 후, 다시 문자하나씩 체크하면서 자신보다 아래(Y+1)에 소문자 블럭 or 공백 블럭이 있는 경우 아래로 내린다. 

       (아래로 내릴때 원래있던 자리는 공백으로 만들어줌)

    4. 1~3을 반복하면서 더이상 사라질 블럭이 없으면 끝



    (참 쉽쥬?)


    항상 알고리즘 문제를 풀때는 점화식이나 어떻게 코딩을 할지 미리 생각한 뒤에 코딩을 해야지 헷갈리지 않고 코드도 안꼬이고 좋습니다.


    자 이제 코드를 살펴 봅시다.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    #include <iostream>
    #include <string>
    #include <vector>
     
    using namespace std;
    int solution(int m, int n, vector <string> board);
    int main(void)
    {
        string arr[] = {"CCBDE""AAADE""AAABF""CCBBF"};
        string arr2[] = {"TTTANT""RRFACC""RRRFCC""TRRRAA""TTMMMF""TMMTTJ"};
        string arr3[] = {"AAAAAAAAAAAAAAA""AAAAAAAAAAAAAAA""AAAAAAAAAAAAAAA""AAAAAAAAAAAAAAA""AAAAAAAAAAAAAAA"};
        string arr4[] = {"AAAAAA""BBAATB""BBAATB""JJJTAA""JJJTAA"};
        vector <string> testCase(arr, arr + (sizeof(arr) / sizeof(arr[0])));
        vector <string> testCase2(arr2, arr2 + (sizeof(arr2) / sizeof(arr2[0])));
        vector <string> testCase3(arr3, arr3 + (sizeof(arr3) / sizeof(arr3[0])));
        vector <string> testCase4(arr4, arr4 + (sizeof(arr4) / sizeof(arr4[0])));
        
        cout << "사라지는 블럭 수 : " <<  solution(45, testCase) << "\n" << endl;
        cout << "사라지는 블럭 수 : " <<  solution(66, testCase2) << "\n" << endl;
        cout << "사라지는 블럭 수 : " <<  solution(515, testCase3) << "\n" << endl;
        cout << "사라지는 블럭 수 : " <<  solution(56, testCase4) << "\n" << endl;
        
        return 0;
    }                                
        
    // 문자 비교(대소문자 구분 x)
    int charCmp(char a, char b)
    {
        if(isupper(a) && isupper(b) && a == b) return 0// a, b 둘다 대문자일때
        else if(isupper(a) && !isupper(b) && a == (b - 32)) return 0// a 대문자 b 소문자 일때
        else if(!isupper(a) && isupper(b) && (a - 32== b) return 0// a 소문자 b 대문자 일때
        else if(!isupper(a) && !isupper(b) && a == b) return 0// a, b 둘다 소문자일때
     
        return 1;
    }
     
    int solution(int m, int n, vector <string> board)
    {
        int answer = 0;
        bool boardChangeFlag = false;
     
        do { // 1. boardChangeFlag == 1일때, board안에 블럭이 사라져서 블럭을 내려야 할 경우
            boardChangeFlag = 0;
            // 2. 사라질 블럭 체크
            for(int i = 0; i < m - 1; i ++) { // m = 높이
                for(int j = 0; j < n - 1; j ++) { // n = 폭
                    if(board[i][j] != ' ' && !charCmp(board[i][j], board[i][j + 1]) && !charCmp(board[i][j], board[i + 1][j]) && !charCmp(board[i][j], board[i + 1][j + 1])) {
                        // 대문자일 경우에 소문자로 변환(인접한 부분을 소문자로 구분짓기 위하여)
                        if(isupper(board[i][j])) {board[i][j] += 32; answer += 1;}
                        if(isupper(board[i][j + 1])) {board[i][j + 1+= 32; answer += 1;}
                        if(isupper(board[i + 1][j])) {board[i + 1][j] += 32; answer += 1;}
                        if(isupper(board[i + 1][j + 1])) {board[i + 1][j + 1+= 32; answer += 1;}
                        boardChangeFlag = true;
                    }
                }
            }
            
            // 3. 빈칸일경우 블럭 내리기 
            if(boardChangeFlag) {
                for(int i = 0; i < n; i ++) { // n = 폭
                    for(int j = m - 2; j >= 0; j --) { // m = 높이
                        for(int k = j; k < m - 1; k ++) { // m(높이)에서 바로 아래에 빈칸이나 소문자블럭이 없을때 까지 밑으로 내림
                            if(board[k + 1][i] == ' ' || !isupper(board[k + 1][i])) { // 소문자(없어져야할 블럭) 이거나 ' '(내릴 블럭)일 경우
                                board[k + 1][i] = board[k][i];
                                board[k][i] = ' ';
                            } else break// 대문자 블럭일 경우 break
                        }
                    }
                }
     
                /******************** 결과 출력 *******************/
                for(int i = 0; i < board.size(); i ++) {
                    cout << board[i] << endl;
                    if(i == board.size() - 1) {
                        for(int j = 0; j < n; j ++cout << '-';
                        cout << '\n';
                    }
                }
            }        
        } while(boardChangeFlag);
     
        return answer;
    }

    전체적인 반복문을 do while문으로 한 이유는 적어도 한번은 블럭을 체크해야 하기 때문에 do while문으로 했습니다.


    저 같은 경우 한번 체크한 문자는 소문자로 만들어 버리기 때문에 따로 문자를 비교하는 함수(charCmp())를 만들어서 사용했습니다. 


    코드안에 (2. 사라질 블럭 체크) 내용을 보시면 맨아래와 맨오른쪽을 제외한 모든 문자를 돌면서 4개의 블럭을 체크합니다. 또한, 블럭이 대문자일 경우에만 +32하여 소문자로 변환해 줍니다.   


    boardChangeFlag 변수는 사라질 블럭이 있다! 그래서 블럭이 아래로 내려와야 한다고 알려주는 flag 변수 입니다.


    (3.빈칸일 경우 블럭 내리기)의 경우 이번 문제의 가장 핵심이라고 볼 수 있습니다. 코드를 그림으로 설명해봤습니다.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    // 3. 빈칸일경우 블럭 내리기 <- 수정 위에서부터 내려야함
    if(boardChangeFlag) {
        for(int i = 0; i < n; i ++) { // n = 폭
            for(int j = m - 2; j >= 0; j --) { // m = 높이
                for(int k = j; k < m - 1; k ++) { // m(높이)에서 바로 아래에 빈칸이나 소문자블럭이 없을때 까지 밑으로 내림
                    if(board[k + 1][i] == ' ' || !isupper(board[k + 1][i])) { // 소문자(없어져야할 블럭) 이거나 ' '(내릴 블럭)일 경우
                        board[k + 1][i] = board[k][i];
                        board[k][i] = ' ';
                    } else break// 대문자 블럭일 경우 break
                }
            }
        }
    }
     

    이러한 동작들이 각 원소(문자)마다 반복하여 실행된다고 보시면 됩니다.


    자! 그럼 출력된 결과를 한번 볼까요?


            


    블럭이 사라질때마다 블럭전체를 출력하여 어떤식으로 사라지는지 볼 수 있게 해봤습니다.


    3번째 테스트에서 'aaaaaaaaaaaaaaa'가 남아있는 이유는 제일 윗쪽 블럭(0번째 줄)은 그 이상(-1)이 없기때문에 위에서 내릴 수가 없습니다. 그래서 저렇게 보이지만 우리가 구하려는 것은 보여지는게 아니라 사라지는 블럭 수를 체크하는 거기때문에 전~~혀 문제가 되지않습니다.


    6번 문제는 상급이긴 한데 그렇게 어렵지는 않은 내용이었네요.(제 코드가 틀리지 않다면요..ㅎㅎ 아마도..!)


    이상으로 오늘의 포스팅을 마치겠습니다. 혹시라도 제 포스팅을 보면서 잘못된 코드나 정정해야 될 부분이 있는 경우 주저하지 마시고 알려주시면 감사하겠습니다~!!:D


    여러분 오늘도 즐거운 코딩하시고 재밌는 코드 생산하세요~~아디오스~:D

    고릴라 이모티콘에 대한 이미지 검색결과

    댓글

운동하는 개발자 JAY-JI