[프로그래머스/JAVA] 프렌즈4블록 - 2018 KAKAO BLIND RECRUITMENT

2018 KAKAO BLIND RECRUITMENT LEVEL 2

LEVEL2인 뉴스클러스터링 문제만 해도 이렇게 까지 오래걸리지는 않았다. 그리고 문제가 나름 길었어도 풀 의욕은 있었는데 이 문제 만큼은 의욕이 떨어졌다. 계속되는 반복문에 일회성 계산이 아닌, 터뜨린 자리는 위에서부터 순차적으로 내려와 메꾸는 알고리즘 형태를 가지고 있어야 했기 때문이다. 물론, 더 나은 알고리즘으로 푼 사람들도 있겠지만 말이다.

대략 이런식의 느낌

중요한건 어떠한 참고서나 메소드 등을 활용하지 않았다는 점에서 문제를 풀었을 때 희열이 있었다.
내가 생각한 이 문제의 핵심적인 부분들은 다음과 같다.

1. 네모 확인하기
---네모 형태가 없으면 break---
2. 확인된 사항의 인덱스를 공백으로 변경(꼭 공백일 필요는 없다.)
3. 공백 메꾸기
4. 1부터 반복

1. 네모 확인하기

네모를 무작정 확인하겠다고 해서 각 꼭지점이 되는 곳을 찾아내 제거하기에도 애매하고, 위의 그림처럼 정사각형 두개가 대각선으로 모이는 부분에서도 찾기가 애매하기 때문에 필자는 정사각형이 되는 부분들을 다 찾아냈다. 그러나 겹치는 부분들이 생겨 두번 제거되는 것을 우려하여 idnex값을 set의 자료구조 안에 넣어 중복되는 index가 발생하지 않도록 주의를 기울였다. 이후 2번으로 넘어가기 전에 네모가 나왔는지 즉, set의 size가 0이 아닌지 확인한 이후에 2번으로 넘어가도록 한다.

2. 확인된 사항의 인덱스를 공백으로 변경

제거된 부분들은 공백으로 통일했다. 이 공백은 위에서부터 순차적으로 내려오는 구간이기 때문에 공백의 파악 여부가 중요하다.

3. 공백 메꾸기

공백된 사항들을 메꾸어야 한다. 그러나 무작정 해당 칸이 공백이면 위에서부터 아래로 불러와주세요 할 수 없는 노릇도 존재한다. 만약 위에 공백밖에 없는데 자신이 공백이라고 해서 계속적으로 불러오면 무한대로 빠질 염려도 있다. 즉, 이 알고리즘을 사용할거면 위에 데이터로 존재하는 칸이 있는지를 확인하고, 위에 있는 모든 칸들이 공백이라면 굳이 위에서부터 불러올 필요가 없어진다.

이후에는 1번부터 반복하는 방법인데 3번까지의 작업을 통해 모든 공백은 데이터가 있는 칸들의 위로 이동하게 되었다. 따라서 모든 데이터들은 아래로 깔려있다고 생각하면 된다. 이제 네모 확인하기 단계부터 다시 시작하게 되는데 이제서야 네모를 확인할 때 중요한 부분이 떠올랐다. 바로 !board[index].equals(" ") 공백으로 사각형이 만들어 지면 안 된다. 사각형이 만들어지는건 상관이 없는데 저 블록들 4개가 같다고 해서 터져야 하는 존재는 아니라는 것이다. 이 부분 체크하고 넘어가자.

문제 해법

import java.util.*;
class Solution {
    public int solution(int m, int n, String[] b) {
        int answer = 0;
        Set<Integer> set = new HashSet<Integer>();
        Iterator<Integer> it;
        String[] board = new String[m * n];
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                board[i * n + j] = Character.toString(b[i].charAt(j));
            }
        }
        while(true) {
            for(int i = 0; i < m - 1; i++) {
                for(int j = 0; j < n - 1; j++) {
                    int index = i * n + j;
                    if(!board[index].equals(" ") &&
                      board[index].equals(board[index + 1]) &&
                      board[index].equals(board[index + n]) &&
                      board[index].equals(board[index + n + 1])) {
                        set.add(index);
                        set.add(index + 1);
                        set.add(index + n);
                        set.add(index + n + 1);
                    }
                }
            }
            if(set.size() == 0) break;
            answer += set.size();
            it = set.iterator();
            while(it.hasNext()) {
                board[it.next()] = " ";
            }
            set.clear();
            for(int i = 0; i < n; i++) {
                for(int j = m - 1; j >= 0; j--) {
                    int index = j * n + i;
                    while(index + n < m * n && board[index + n].equals(" ")) {
                        board[index + n] = board[index];
                        board[index] = " ";
                        index = index + n;
                    }
                }
            }
        }
 
        return answer;
    }
}