[프로그래머스] 2018 KAKAO BLIND RECRUITMENT[1차] 프렌즈4블록

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

프로그래머스

 

해당 문제는 애니팡과 비슷한 게임이라고 생각할 수 있습니다.

풀이의 핵심은 두가지로 나눌 수 있습니다.

1. 인접한 2x2 사각형의 모든 블록의 종류가 같은지 파악하여 터질 블록을 판단

2. 블록을 터뜨린 후, 터뜨린 블록 윗 블록들에 대해 아래로 내리기

 

문제를 풀면서 c++에는 있는 tuple이나 pair자료구조에 대해 java는 왜없는지..조금 안타까웠습니다.

좌표에 대해 int[] 배열로 Set에 넣으면 equals와 hashCode를 재정의할 수 없기 때문에 Set에서는 중복으로 판단할 수 없습니다.

 

따라서 따로 Node class를 정의해준 후에, Node 클래스 내부에 equals와 hashCode를 재정의하여 Set에서 중복요소를 거를수 있게끔 구현했습니다.

 

또, 블록을 터뜨린 후 나머지 블록을 아래로 내리는 구현으로는 String클래스의 format과 인스턴스 메서드인 replace를 적절하게 사용해서 아래와 같은 논리로 최대한 간결하게 구현했습니다.

 

1. 터진 블록의 칸을 '-'로 처리

2. 터진 블록이 있는 열에 대해 '-'지우기

3. String format을 길이를 m으로 제한한 후 오른쪽 정렬,

4. 왼쪽의 채워진 공백 ' '을 '-'로 재갱신

 

//코드

import java.util.*;

class Solution {
    public class Node{
        int x, y;
        
        Node(int x, int y){
            this.x = x;
            this.y = y;
        }
        @Override
        public int hashCode(){
            int ret = 31 * this.x + this.y;
            return ret;
        }
        
        @Override
        public boolean equals(Object obj){
            Node n = (Node) obj;
            return n.x == this.x && n.y == this.y;
        }
    }
    
    public int solution(int m, int n, String[] board) {
        int answer = 0;
        
        char[][] chars = new char[m][n];
        for(int i=0; i<m; i++){
            chars[i] = board[i].toCharArray();
        }
        answer = solve(m, n, chars);
        return answer;
    }
    
    
    int solve(int m, int n, char[][] chars){
        
        Set<Node> set = new HashSet<>();
        
        //팡! 탐색
        for(int i=0; i<m-1; i++){
            for(int j=0; j<n-1; j++){
                if(chars[i][j] == '-') continue;
                if(chars[i][j]==chars[i+1][j] && chars[i][j] == chars[i][j+1] && chars[i][j] == chars[i+1][j+1]){
                    set.add(new Node(i, j));
                    set.add(new Node(i+1, j));
                    set.add(new Node(i, j+1));
                    set.add(new Node(i+1, j+1));
                }
            }
        }
        
        //팡의 개수가 0이라면 return;
        int pang = set.size();
        if(pang == 0) return 0;
        //팡 처리
        for(var v: set){
            chars[v.x][v.y] = '-';
        }
        
        //블록 내리기
        for(int j=0; j<n; j++){
            String line = "";
            for(int i=0; i<m; i++) line += chars[i][j];
            line = String.format("%" + m + "s", line.replace("-", "")).replace(" ", "-");
            for(int i=0; i<m; i++) chars[i][j] = line.charAt(i);
        }
        
        //현재 팡의 개수 + 다음 팡의 개수 return
        return pang + solve(m, n, chars);
    }
}