[프로그래머스/Level2] [1차] 프렌즈4블록

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• 시뮬레이션

1. 정사각형인 부분을 찾아 정사각형인 부분이 존재한다면,  집합(Set)에 해당 좌표들을 저장한다. (findSquares())

2. 정사각형 위치 집합을 돌며 해당 위치의 블록들을 제거한다. (= '.'으로 변경)

3. 중력을 적용시킨다.

private static void dropBlocks() {
    // 1. 2차원 임시 배열 생성해 모두 빈 칸(.)으로 초기화하기
    char[][] tmpGrid = new char[m][n];
    for(int i = 0 ; i < m ; i++) {
        for(int j = 0 ; j < n ; j++) {
            tmpGrid[i][j] = '.';
        }
    }

    // 2. 2차원 임시배열 채워넣기 (중력 적용)
    for(int col = 0 ; col < n ; col++) {
        int tmpRow = m - 1;

        for(int row = m - 1 ; row >= 0 ; row--) {
            if(grid[row][col] != '.') {
                tmpGrid[tmpRow][col] = grid[row][col];
                tmpRow--;
            }                    
        }
    }

    // 3. 임시 배열의 값을 원본 배열에 복사하기
    for(int i = 0 ; i < m ; i++) {
        for(int j = 0 ; j < n ; j++) {
            grid[i][j] = tmpGrid[i][j];
        }
    }         
}

 

 

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static int m,n;
    static String[] board;
    static char[][] grid;
    
    public int solution(int m, int n, String[] board) {
        this.m = m;
        this.n = n;
        this.board = board;
        
        grid = new char[m][n];
        for(int i = 0 ; i < board.length ; i++) {
            for(int j = 0 ; j < board[i].length() ; j++) {
                grid[i][j] = board[i].charAt(j);
            }
        }
        
        while(true) {
            // 1. 정사각형인 부분 있는지 검사하기
            Set<int[]> set = findSquares();            
            if(set.isEmpty())   break; // 정사각형 없다면 종료
            
            // 2. 정사각형인 부분 제거하기 (.으로 변경)
            for(int[] p : set) {
                grid[p[0]][p[1]] = '.';
            }
            
            // 3. 끌어내리기
            dropBlocks();
        }
 
        int answer = 0;
        for(char[] ch : grid) {
            for(char c : ch) {
                if(c == '.')
                    answer++;
            }
        }
        
        return answer;
    }
 
    // 정사각형에 속하는 좌표 저장하는 집합 만드는 메서드
    private static Set<int[]> findSquares() {
        Set<int[]> tmpSet = new HashSet<>();
        
        for(int i = 0 ; i < m - 1 ; i++) { 
            for(int j = 0 ; j < n - 1 ; j++) {
                if(grid[i][j] != '.' && isSquare(i, j)) {
                    tmpSet.add(new int[]{i,j});
                    tmpSet.add(new int[]{i+1,j});
                    tmpSet.add(new int[]{i,j+1});
                    tmpSet.add(new int[]{i+1,j+1});
                }
            }
        }  
        
        return tmpSet;
    }
 
    // 중력 적용 메서드
    private static void dropBlocks() {
        // 2차원 임시 배열 생성해 모두 빈 칸으로 초기화하기
        char[][] tmpGrid = new char[m][n];
        for(int i = 0 ; i < m ; i++) {
            for(int j = 0 ; j < n ; j++) {
                tmpGrid[i][j] = '.';
            }
        }
 
        // 2차원 임시배열 채워넣기
        for(int col = 0 ; col < n ; col++) {
            int tmpRow = m - 1;
 
            for(int row = m - 1 ; row >= 0 ; row--) {
                if(grid[row][col] != '.') {
                    tmpGrid[tmpRow][col] = grid[row][col];
                    tmpRow--;
                }                    
            }
        }
 
        // 임시 배열의 값을 원본 배열에 복사하기
        for(int i = 0 ; i < m ; i++) {
            for(int j = 0 ; j < n ; j++) {
                grid[i][j] = tmpGrid[i][j];
            }
        }         
    }
 
    // 2*2 정사각형 이루는지 판별하는 메서드
    private static boolean isSquare(int x, int y) {  
        return (grid[x][y] == grid[x+1][y] && grid[x][y] == grid[x][y+1] && grid[x][y] == grid[x+1][y+1]);
    }
}

 

 

---

💦 어려웠던 점

약 1시간 소요

- 정사각형에 속하는 좌표들 갯수(set.size())를 정답에 더하니 틀렸었다.🤔 → 빈 칸 = '.'으로 변경된 칸의 수를 구해 정답에 더하니 맞았다.

- 위쪽의 빈 공간 '.' 인 부분 처리 → 애초에 2차원 임시배열의 모든 값을 빈 칸(.)으로 초기화 하고, 값이 들어있는 값에 대해서만 중력 적용시켜 해당 값으로 채우기

 

 

1회독	2회독	3회독	4회독	5회독
V