[프로그래머스/자바] 프렌즈4블록 풀이 - 2018 KAKAO BLIND RECRUITMENT

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

프로그래머스

 

2018 KAKAO BLIND RECRUITMENT 1차 Level 2 문제다.

 

 

단순히 2차원 배열을 다루는 구현 문제다.

while(true)로 무한루프를 돌면서, while문을 한번 돌 때마다 삭제할 2x2 블록을 찾는다.

만약에 삭제할 블록이 없다면 while을 빠져나오는 식이다.

삭제할 블록이 없을 때까지 반복하는 것이다.

 

 

먼저 String 1차원 배열 board를 편하게 접근하기 위해 

문자열 하나하나씩 쪼개 2차원 배열 new_board 안에 넣었다.

 

while문 안에서 new_board의 원소들을 탐색하면서 

현재 원소, 오른쪽, 아래, 오른쪽 아래가 모두 같은 부분을 찾는다.

한번 검사할 때 4개의 원소를 다 확인하므로 n*m만큼 다 탐색하는 것이 아닌

n-1*m-1만큼 탐색해도 모든 원소를 확인하는 것과 동일하다.

블록이 모두 같은 2x2 블록을 찾았다면 2x2에 해당하는 블록 4개 모두 delete[][]를 true로 설정한다.

 

new_board를 모두 탐색한 후, delete[][]가 true인 블록을 찾는다.

true인 블록은 삭제할 블록이므로 위에 블록이 아래로 내려와야 한다.

만약 삭제할 블록이 가장 위에 있다면 블록을 내리지 않고 바로 삭제처리 한다. 

나는 삭제된 블록을 *로 변경했다.

삭제할 블록이 위에 있지 않다면 삭제할 블록 보다 위에 있는 모든 블록을 한칸씩 내린다.

한칸씩 내렸다는 것은 가장 위에 빈칸이 생겼다는 의미와 같으므로 new_board[0][y] 를 삭제처리 한다.

 

입출력 예제 1과 같이 2x2 블록이 겹치는 경우가 있더라도

삭제해야 할 블록을 delete[][] = true로 설정하기 때문에 삭제된 블록의 갯수는 한번만 반영된다.

 

 

class Solution {
    static char[][] new_board;
    
    public int solution(int m, int n, String[] board) {
		int ans = 0;
		new_board = new char[m][n];

		for(int i=0;i<m;i++)
			for(int j=0;j<n;j++) 
				new_board[i][j] = board[i].charAt(j);

		while(true) {
			boolean[][] delete = new boolean[m][n];

			// 2x2 블록 찾기
			for(int i=0;i<m-1;i++) { 
				for(int j=0;j<n-1;j++) { 
					char c = new_board[i][j];
					if(c == '*')
						continue;
					if(new_board[i][j + 1] == c && new_board[i + 1][j] == c && new_board[i + 1][j + 1] == c) {
						delete[i][j] = true;
						delete[i][j + 1] = true;
						delete[i + 1][j] = true;
						delete[i + 1][j + 1] = true;
					}
				}
			}

			int del = 0;
			for(int i=0;i<m;i++) {
				for(int j=0;j<n;j++)
					if(delete[i][j]) {
						del++;
						deleteBlock(i, j);
					}
			}

			// 지워진 블록이 없다면 while문 빠져나오기
			if(del == 0)
				break; 
			ans += del;
		}

		return ans;
	}

	static void deleteBlock(int x, int y) {
		if(x == 0) { // 가장 윗 행이면 바로 블록 지우기 (지워진 블록은 * 표시)
			new_board[x][y] = '*';
		}
		else {
			// 위에 있는 행을 아래로 한칸씩 내리고 가장 윗 행에 있는 블록 지우기
			for(int i=x-1;i>=0;i--) 
				new_board[i + 1][y] = new_board[i][y];
			new_board[0][y] = '*';
		}
	}
}