[Java/프로그래머스] 프렌즈4블록 (10번 케이스 해결)

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

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

문제설명은 위 링크에서 확인가능, 10번 케이스에 대한 설명은 <내리기 함수> 설명에 있다.

나에게 이 문제의 교훈은 모든 케이스를 다 고려해서 알고리즘을 작성해야한다는 것이다.

<전체적인 문제해결 방식>

나는 이 문제가 구현 시뮬레이션 문제라고 해석했다.

2차원 char배열로 만들고

탐색과 내리기를 반복하다가, 탐색했는데 더이상 지울 것이 없다면 답을 구한다.

<탐색함수>

0~m-1과 0~n-1 인덱스 조합을 이중 for문으로 확인한다.

i, j를 기준으로 

  (i, j)     (i, j+1)

(i+1, j) (i+1, j+1)

이렇게 네개가 같으면 4개 칸 모두 chcek에 true로 기록하고 (물론 내리기 함수에서 넣은 쓰레기값은 같아도 무시한다.)

그리고 j열과 j+1열도 isExist에 true로 기록한다.

그리고 탐색 성공여부 함수 리턴인 flag 변수도 true로 기록한다.

따라서 지워질 칸과 열 그리고 탐색에 성공했는지 여부를 알 수 있다.

<내리기 함수>

제일 바깥에 열을 기준으로 for문

그 안에 행으로 움직일 것인데, 

먼저 isExist가 true면 그냥 다음열을 확인하면된다. 왜냐하면 움직일 게 없기 때문이다.

isExist가 false면 지울 게 있다는 말이니까 계속한다.

먼저 아래부터 확인하며 최초로 발견되는 지워질 칸을 찾는다. (check배열에 true로 기록된 칸들)

그리고 나서 그 칸부터 최조로 발견되는 아래로 옮겨질 칸을 찾는다.(check배열에 false로 기록된 칸들)

1. 아래로 옮겨질 칸에 있는 값을 지워질 칸으로 옮기고

2. 아래로 옮겨질 칸에는 쓰레기값을 넣어서 탐색함수에서는 무시하게한다. 

1, 2번을 인덱스 0을 벗어날 때까지 --하며 반복한다.

근데 해당 열에 지워지는 게 띄엄띄엄 있는 경우

ex) 

T 0

T 1

F 2

F 3

T 4

T 5

F 6

3를 5로 옮기고 3에 쓰레기값넣고

2를 4로 옮기고 2에 쓰레기값넣고

1을 3으로 옮기고 1에 쓰레기값 넣고 (??? 이러면 안된다!! 0도 2로 옮기는 게 아니다!!)

0과 1은 지워지는 칸이므로 쌓으면 안되고 건너뛰어야한다! 이때 위의 인덱스만 움직여야한다.

위 과정을 마치면 지워지지 않은 (즉, check에 false값이 있는) 칸은 다 아래로 차곡차곡 쌓이게된다.

그러므로 이제 차곡차곡 쌓은것 위의 것들은 다 쓰레기값을 넣어주면된다.

 

마지막에는 쓰레기값의 갯수를 세어준면 답을 구할 수 있다.

 

 

빨간색 문장으로 써놓은 케이스를 간과해서 10번만 계속 틀리고 계속 고민하다가 결국 아래 질문글을 확인하고 해결했다.

https://programmers.co.kr/questions/13147

/*
 * PGM 프렌즈4블록 https://programmers.co.kr/learn/courses/30/lessons/17679#
 * 일단 char 2차원 배열로 바꾼다.
 * 그리고 탐색하고 위에 것 내리며 지우는 과정을 반복하다가 지워지는 것이 없으면 끝
 */
class Solution {
    static boolean[] isExist;
    public int solution(int m, int n, String[] board) {
        char[][] arr = new char[m][n];
        boolean[][] check = new boolean[m][n];
        isExist = new boolean[n];
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                arr[i][j] = board[i].charAt(j);
            }
        }
        
        while(searchSquare(arr, check, m, n)) {
            downShift(arr, check, m, n);
            check = new boolean[m][n];
            isExist = new boolean[n];
        }
        
        int answer = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(arr[i][j] == '0')
                    answer++;
            }
        }
        return answer;
    }
    static boolean searchSquare(char[][] arr, boolean[][] check, int m, int n) {
        boolean flag = false;
        for(int i = 0; i < m-1; i++) {
            for(int j = 0; j < n-1; j++) {
                if(arr[i][j] == '0' || arr[i+1][j] == '0'
                  || arr[i][j+1] == '0' || arr[i+1][j+1] == '0')
                    continue;
                
                if(arr[i][j] == arr[i][j+1] 
                    && arr[i][j+1] == arr[i+1][j] 
                    && arr[i+1][j] == arr[i+1][j+1]) {
                    flag = true;
                    check[i][j] = true;
                    check[i][j+1] = true;
                    check[i+1][j] = true;
                    check[i+1][j+1] = true;
                    
                    isExist[j] = true;
                    isExist[j+1] = true;
                }
            }
        }
        return flag;
    }
    static void downShift(char[][] arr, boolean[][] check, int m, int n) {
        for(int i = 0; i < n; i++) { //열 먼저
            if(!isExist[i]) continue; // 지워진 칸이 없다면 다음 열 확인
            
            int startT = -1;
            int startF = -1;
            
            for(int j = m-1; j >= 0; j--) { //한 열에서 밑에서부터 행을 확인
                if(check[j][i]) { //지워진 칸을 만나면 멈춤
                    startT = j;
                    break;
                }
            }
            for(int j = startT-1; j >= 0; j--) {
                if(!check[j][i]) { //지워진 칸 만난 후에 다시 안지워진 칸을 만나면 멈춤
                    startF = j;
                    break;
                }
            }
            
            //System.out.println(startT+" "+startF);
            while(startF >= 0) { //이동하며 원래자리에 쓰레기값을 넣어준다.
                if(check[startF][i]) { //F - T - F - T가 반복될 수 있으니
                    startF--;
                    continue;
                }
                arr[startT][i] = arr[startF][i];
                arr[startF][i] = '0';
                startT--;
                startF--;
            }
            //이제 위는 다 비었으니 모두 쓰레기값을 넣어줘서 더이상 확인 안하게한다.
            while(startT >= 0) {
                arr[startT][i] = '0';
                startT--;
            }
        }
    }
}