[201221] 프렌즈4블록 - 2018 KAKAO BLIND RECRUITMENT

0. 문제유형 : 반복문, 배열 탐색

1. 문제이해

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

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

2x2 블록

해당 블록을 지우고 아래로 내림

(1) 주요 요구사항

: 같은 모양의 블록이 2x2 형태로 붙어 있으면 지워지면서 점수를 얻는 게임

- 같은 블록은 여러 2x2에 포함 가능

- 가능한 경우의 블록을 모두 지운 후 위에 있는 블록은 아래로 떨어짐

▶ 더 이상 지울 수 없을 때까지 반복. 과정 중 지워지는 블록 개수 합 return.

 

(2) 제한사항

- 높이 m, 폭 n인 board는 2차원 배열이 아닌 문자열로 이루어진 1차원 배열로 주어짐 (**실수로 간과했던 사실)

ex> [CCBDE, AAADE, AAABF, CCBBF]

- 중복되어 사라지는 블록이여도 개수는 한 번만 포함

 

 

2. 전략

(1) erase 메소드 : 같은 모양의 2x2 블록 찾고 지우기

- 왼쪽 상단 블록을 기준으로 오른쪽, 아래, 대각선과 비교 진행

- 모두 같다면? HashSet에 해당 인덱스 [i,j]를 i*n + j 형태로 넣어준다.

(이유 : 중복되어 사라지는 블록의 개수를 세기 위해)

※ 단, 원소가 없음을 나타내는 'X'는 포함될 수 없다.

- 해당 HashSet에 있는 원소들은 'X'로 변경하여 지워준다.

 

(2) move 메소드 : 블록을 아래로 이동

- char[][] answer : board의 원소들을 조정한 결과를 담을 배열

- 이동 규칙

1. 열 단위로 하단(board[m-1][i])부터 위쪽 방향으로 원소를 확인한다.
- 원소가 'X'라면? 다음 루프로 continue
- 아니라면? answer의 하단부터 원소를 채운다.
2. answer의 나머지 공간은 'X'로 채운다.

 

 

3. 참고사항

(1) 2차원 배열로 변환

board2[i] = board[i].toCharArray();

 

(2) erase 메소드 : HashSet 대신 표시만으로도 판별 가능

- 왼쪽 상단 블록부터 확인한 것이므로 이후 시행될 비교에서 다시 비교되지 않음

: 왼쪽 상단 블록만 'Y'로 미리 바꿔도 괜찮음

- 지워지는 블록 개수 세기

: 'Y'인 블록 찾아서 하나씩 'X'로 바꾸면서 개수 세기

 

 

4. 코드

import java.util.*;

class Solution {
    int answer;
    boolean flag;
    public int solution(int m, int n, String[] board) {
        answer = 0; flag = true;
        char[][] board2 = new char[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                board2[i][j] = board[i].charAt(j);
            }
        }
        while(flag){
            board2 = erase(m, n, board2);
        }
        return answer;
    }
    
    public char[][] erase(int m, int n, char[][] board){
        HashSet<Integer> set = new HashSet<>();
        for(int i = 0; i < m-1; i++){
            for(int j = 0; j < n-1; j++){
                char target = board[i][j];
                if(target != 'X' && target == board[i][j+1] 
                   && target == board[i+1][j] && target == board[i+1][j+1]){
                    set.add(i*n+j); set.add(i*n+j+1);
                    set.add((i+1)*n+j); set.add((i+1)*n+j+1);
                }
            }
        }
        if(set.size() == 0) flag = false;
        else{
            answer += set.size();
            Iterator<Integer> itr = set.iterator();
            while(itr.hasNext()){
                int num = itr.next();
                board[num/n][num%n] = 'X';
            }
            board = move(m, n, board);
        }
        return board;
    }
    
    public char[][] move(int m, int n, char[][] board){
        char[][] answer = new char[m][n];
        for(int i = 0; i < n; i++){
            int index = m-1;
            for(int j = m-1; j >= 0; j--){
                if(board[j][i] == 'X')  continue;
                else{
                    answer[index--][i] = board[j][i];
                }
            }
            while(index >= 0)    answer[index--][i] = 'X';
        }
        return answer;
    }
}