프렌즈4블록

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

프로그래머스

 

 

블록이 4개가 모이면 지워지고, 그 4개 위에 있던 블록이 아래로 내려와야한다.

처음엔 stack으로 풀어나갔는데, 젤 윗라인 뿐만 아니라 그 아래 라인의 블록들도 신경써야 하므로 List로 처리했다.

 

주어진 String[] 타입의 board를 쉽게 풀기 위해 List<Character>[] 형태로 변환했는데, 

board에서 array가 행을 나타내고, string이 하나의 행을 구성하는 열을 나타내는데

새로 변환한 blocks는 array가 열을 나타내고, List가 하나의 열을 구성하는 행을 나타낸다.

그래야 블록을 제거했을 때, 그 블록 위에 있던 블록이 아래로 내려오는것과 같은 효과를 볼 수 있다.

 

그리고 블록이 정사각형의 형태로 배치되어있더라도 즉시 제거하지 않고 cache에 모아두었다. 즉시 제거하는 경우 3*2 개의 배치로 구성된 블록은 2*2개만 제거되고 나머지 두개는 제거되지 않는다.

 

이렇게 모아둔 cache는 List 기준 역순 정렬하여 원소를 제거(remove)하더라도 엉뚱한 원소가 제거되는 일을 막아야 한다.

 

import java.util.*;

class Solution {
    public int solution(int m, int n, String[] board) {
        
        int answer = 0;
        
        List<Character>[] blocks = init(m, n, board);
        
        SortedSet<int[]> cache = new TreeSet<> ((a, b) -> {
            int compare = a[0] - b[0];
                if (compare == 0) {
                    compare = b[1] - a[1];
                }
                return compare;
        });
        
        boolean refresh = true;
        while (refresh) {
            refresh = false;
            
            for (int i = 0; i < n - 1; i++) {
            
                for (int j = 0; j < m - 1; j++) {

                    if (removable(blocks, i, j)) {
                        
                        cache.add(new int[] {i, j});
                        cache.add(new int[] {i, j + 1});
                        cache.add(new int[] {i + 1, j});
                        cache.add(new int[] {i + 1, j + 1});
                        
                        refresh = true;

                    }

                }

            }
            
            cache.forEach(c -> {
                blocks[c[0]].remove(c[1]);
            });
            
            answer += cache.size();
            cache.clear();
            
            // print(blocks);
            
        }
        
        return answer;
        
    }
    
    void print(List<Character>[] blocks) {
        
        System.out.println("===");
        
        for (int i = 0; i < blocks.length; i++) {
            
            for (int j = 0; j < blocks[i].size(); j++) {
                
                System.out.print(blocks[i].get(j));
                
            }
            
            System.out.print("\n");
            
        }
        
    }
    
    boolean removable(List<Character>[] blocks, int i, int j) {
        
        if (blocks[i].size() <= j + 1) {
            return false;
        }
        
        char block = blocks[i].get(j);
        
        char b = blocks[i].get(j + 1);
        if (block != b) {
            return false;
        }
        
        List<Character> rightCols = blocks[i+1];
        if (rightCols.size() <= j + 1) {
            return false;
        }
        
        char r = rightCols.get(j);
        if (block != r) {
            return false;
        }
        
        char rb = rightCols.get(j+1);
        if (block != rb) {
            return false;
        }
        
        return true;
        
    }
    
    List<Character>[] init(int m, int n, String[] board) {
        List<Character>[] blocks = new List[n];
        for (int i = 0; i < n; i++) {
            blocks[i] = new ArrayList();
        }
        
        for (int i = m - 1; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                blocks[j].add(board[i].charAt(j));
            }
        }
        
        return blocks;
    }
}