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

작성일: 2024-11-18

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/17679

접근 방식

탐색을 이용한 구현문제다. 문제에 나와있는 순서대로 차근히 구현한다면 어렵지 않은 문제다.

먼저 삭제할 블록을 체크한다.
선택된 블록을 삭제하고, 만약 삭제한 블록이 0개라면 로직을 종료한다.
0개가 아니라면 answer에 더하고, 로직을 반복한다.

결과

소스 코드

import java.util.*;

class Solution {
    public int solution(int m, int n, String[] board) {
        int answer = 0;
        // char 배열로 변환
        char[][] arr = new char[m][n];
        for(int i=0; i<m; i++){
            arr[i] = board[i].toCharArray();
        }
        while(true){
            // 삭제할 블록 체크
            boolean[][] tmp = delete(m, n, arr);
            // 블록 삭제하고 개수 세기
            int removedBlocks = countBlocks(m, n, tmp, arr);
            // 0개라면 while문 종료
            if(removedBlocks==0) break;
            // total에 더하기
            answer+=removedBlocks;
            // 정렬하기
            align(m, n, arr);
        }

        return answer;
    }

    // 삭제할 블록 체크
    boolean[][] delete(int m, int n, char[][] arr){
        boolean[][] tmp = new boolean[m][n];
        for(int i=0; i<m-1; i++){
            for(int j=0; j<n-1; j++){
                char target = arr[i][j]; // 선택한 캐릭터
                if(target!='X' && target==arr[i][j+1] && target==arr[i+1][j] && target==arr[i+1][j+1]){
                    tmp[i][j] = true;
                    tmp[i][j+1] = true;
                    tmp[i+1][j] = true;
                    tmp[i+1][j+1] = true;
                }
            }
        }
        return tmp;
    }

    // 삭제된 블록 세기
    int countBlocks(int m, int n, boolean[][] tmp, char[][] arr){
        int cnt = 0;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(tmp[i][j]){
                    arr[i][j] = 'X';
                    cnt++;
                }
            }
        }
        return cnt;
    }

    // 정렬하기
    void align(int m, int n, char[][] arr){
        for(int i=0; i<n; i++){
            List<Character> list = new ArrayList<>();
            for(int j=m-1; j>=0; j--){
                if(arr[j][i]!='X'){
                    list.add(arr[j][i]);
                }
            }
            int idx = m-1;
            for(char l:list){
                arr[idx--][i]=l;
            }
            for(int k=idx; k>=0; k--){
                arr[k][i]='X';
            }
        }
    }
}

코드는 길지만 총 세가지 로직을 통해 블록을 제거한다.

1. 삭제할 블록 체크
2. 블록 삭제하고, 삭제한 블록 개수 세기
3. 삭제된 블록이 있다면, 블록 정렬시키기

먼저,삭제할 블록 체크의 경우, 삭제 블록을 발견하고 바로 삭제하면 안 된다.
그림에도 나와있듯이, 삭제할 블록이 서로 중복되더라도 상관이 없는 것으로 판단하기 때문에 삭제 블록이 나오고 바로 삭제해버리면 문제의 요구사항을 충족하지 못할 것이다.

2번 로직은 쉽다. 삭제할 블록을 체크했으니, 해당 블록을 만나면 삭제처리를 하고, 블록 개수를 세서 리턴하면 된다.

3번 로직이 살짝 복잡할 수 있다. 먼저 열을 기준으로 정렬을 진행해야 한다.
그리고 삭제되지 않은 블록은 아래에서부터 쌓여야하고, 삭제된 블록은 위로 가야한다. 따라서 아래서부터 삭제하지 않을 블록을 체크해야한다.
체크된 블록을 기준으로 해당 열의 값을 정리하고, 남은 열은 X로 채운다.

다른 접근 방식

없음.

느낀 점

없음.