[2018 KAKAO BLIND RECRUITMENT] [1차] 프렌즈4블록 for JAVA

https://programmers.co.kr/learn/courses/30/lessons/17679

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

https://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/

카카오 신입 공채 1차 코딩 테스트 문제 해설

[문제 설명]

프렌즈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가 사용된다.

출력 형식

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

입출력 예제

m	n	board	answer
4	5	[CCBDE, AAADE, AAABF, CCBBF]	14
6	6	[TTTANT, RRFACC, RRRFCC, TRRRAA, TTMMMF, TMMTTJ]	15

예제에 대한 설명

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

[풀이]

나는 주어진 조건을 통해 차례대로 코딩을 하여 문제풀이를 하였다.

아래는 내가 문제를 푼 방법의 순서를 나열해봤다.

 

• 먼저 m, n의 높이, 길이만큼 char형 배열을 선언해준다.
• board판에 있는 내용으로 배열을 채워준다.
• 2x2사각형을 기준으로 해야하게 때문에 i 와 j를 1로 시작하여 왼쪽, 위, 왼쪽 위의 알파벳이 모두 일치한지 판단하고 만약 같다면 알파벳들을 소문자로 만들어준다. (문제 조건에 모든 문자는 대문자로 주어지기 때문에 가능하다.)
• 근데 알파벳은 같은데 소문자가 되있는 문자가 있다면 (4 - 소문자 개수)를 해준 결과를 result에 더해준다. 왜냐면 이미 소문자는 전 단계에서 이미 없어진 것으로 카운터가 되어 값이 추가 됐으므로 중복 추가를 방지하기 위해서이다.
• 위의 과정이 마무리 된 배열은 소문자를 0으로 바꿔주는 작업을 거치게 된다. 
• 이제 위에서 부터 아래로 정렬을 해준다. 현재 문자가 대문자이고, 아래 문자가 '0'이라면 바꿔준다.
• 위의 과정을 배열안에서 0이 안나올 때까지 해준다. (0이 안나옴은 깨진 블록이 없음을 의미하니까)

[코드]

public int solution(int m, int n, String[] board) {
        // m높이 n넓이
        char[][] map = new char[m][n];
        int result = 0;
 
        for (int i = 0; i < m; i++) { // 게임판 초기화
            for (int j = 0; j < n; j++) {
                map[i][j] = board[i].charAt(j);
            }
        }
        boolean flag = true;
        while (flag) {                                                            //더 이상 뿌셔지는게 없으면 종료
            for (int i = 1; i < m; i++) {
                for (int j = 1; j < n; j++) {
                    char temp = map[i][j];                                         // 오른쪽 아래 블록
                    int mCount = 0;                                             // 1의 개수
                    if (temp == '0')
                        continue;                                                 // 이미 삭제 됬으면 패스
 
                    if ((map[i][j - 1] == temp || map[i][j - 1] == temp + 32)
                            && (map[i - 1][j] == temp || map[i - 1][j] == temp + 32)
                            && (map[i - 1][j - 1] == temp || map[i - 1][j - 1] == temp + 32)) { // 4개가 다 같으면
                        if (map[i][j - 1] == temp + 32)         mCount++;                             // 이미 포함되있는 부분 체크
                        if (map[i - 1][j] == temp + 32)         mCount++;
                        if (map[i - 1][j - 1] == temp + 32)  mCount++;
 
                        if (map[i][j - 1] == temp)         map[i][j - 1] = (char) (temp + 32);     // 이미 없어졌다는 것을 체크
                        if (map[i - 1][j] == temp)      map[i - 1][j] = (char) (temp + 32);
                        if (map[i - 1][j - 1] == temp)    map[i - 1][j - 1] = (char) (temp + 32);
                        map[i][j] = (char) (temp + 32);            
                        result += (4 - mCount);                                                    //(4 - 이미 없어진 곳)
                    } else {
                        continue;
                    }
                }
            }
            
            flag = !flag;
            for (int i = 0; i < m; i++) {                                                         // 뿌서진 부분 0으로 초기화
                for (int j = 0; j < n; j++) {
                    if (map[i][j] >= 97) {
                        map[i][j] = '0';
                        flag = true;
                    }
                }
            }
            for (int i = 0; i < n; i++) {                                                         // 없어진 블록 맨 위로 보내기
                for (int j = 0; j < m; j++) {
                    char temp = ' ';
                    for (int k = 0; k < m - 1; k++) {
                        if (!(map[k][i] >= 97) && map[k + 1][i] == '0') {                         // 밑에 있는 애가 파괴된 애면 바꿈
                            temp = map[k][i];
                            map[k][i] = map[k + 1][i];
                            map[k + 1][i] = temp;
                        }
                    }
                }
            }
        };
 
        return result;
    }

 

느낀 점: 프로그래머스 기준 level2라 조금 쉽게 풀었던 것 같다. 하지만 String 2차원배열을 썼으면 어땠을까라는 아쉬움이 있고 조금 효율적인 알고리즘을 알았다면 이렇게 길게 안했을텐데라는 아쉬움이 있었다. 나중에 조금 실력이 더 올라갔을 때 한번 더 풀어보면서 더 좋은 풀이방향으로 문제를 풀어봐야겠다.