Lv.2 프렌즈4블록 [JAVA]

문제 링크

성공 여부(걸린 시간): 성공(27분18초)

아이디어

문제를 읽다보니 주어지는 문자열의 길이도 짧아서 시간도 넉넉하고 단순 구현문제라고 생각했다.

전체코드의 전반적인 순서는 이러하다.

map 생성

-> (탐색 -> 삭제 -> 블럭 떨어뜨리기) 새로 탐색되는 2 * 2블럭이 없을 때까지 반복

-> 삭제처리된 블럭 개수 세고 return

여기서 반복문을 dowhile문을 써서 우선 한번 돈 다음 그 결과로 조건을 검사하고 싶었지만

아쉽게도 do while문의 문법이 기억이 안나서 내 방식대로 풀었다.

 

(탐색 -> 삭제 -> 블럭 떨어뜨리기) 반복문이 사실 이 문제풀이의 핵심 로직인데

여기서 주의할 점은 2 * 2 블럭을 찾더라도 그 즉시 삭제하면 안된다.
내가 탐색-> 삭제 순서로 구분해둔 이유인데 아래의 그림을 보면 이해가 빠를 것이다.

겹치는 부분이 존재할때 미리 삭제하고 지나가버리면 추후에 검출에서 문제가 생긴다.
그래서 나는 삭제를 remove라는 HashSet에 검출된 2 * 2 블록의 제일 왼쪽 상단 좌표를 저장해주었다.

그래서 이러한 점들을 미리 발견했다면 그 이후로는 힘들게 없다.

 

탐색은 단순하게 2중 for문으로 내 현재 좌표의 아래, 오른쪽, 오른쪽 아래(대각선)의 좌표에 해당하는 문자가 같다면
검출된 것이므로 remove에 String타입으로 현재좌표를 x+" "+y 이렇게 넣어준다.

 

그다음 삭제도 또한 간단하다.
map배열에서 저장된 좌표들의 현재 좌표와 현재 좌표의 아래, 오른쪽, 오른쪽 아래(대각선)의 좌표에 '.'를 넣어준다.

그다음 블럭을 아래로 떨어뜨리는 것인데 이부분은 아이디어가 다양할 것 같은데 나는 이렇게 처리했다.
우선 열마다 ArrayList를 생성해주고 ArrayList에 해당열의 제일 하단 부터 '.'를 제외한 문자를 순서대로 넣어줬다.
그다음 해당 ArrayList를 개수만큼 순회하며 map에 해당 열의 아래부터 채워주면 끝이다.
열의 개수만큼 반복하면 끝!

 

그렇게 더이상 검출이 안되어 모든 반복이 끝나면 '.'의 개수를 세어서 return해주면 끝이다.

정답 코드

import java.util.*;
class Solution {
    public int solution(int m, int n, String[] board) {
        int N = board.length;
        int M = board[0].length();
        char [][] map = new char[N][M];
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                map[i][j] = board[i].charAt(j);
            }
        }
        HashSet<String> remove= new HashSet<>();
        remove.add("hi");//do while문을 못써서 조건을 통과하기 위한 임시값
        while(remove.size()!=0){
            remove = new HashSet<>();
            //검출
            for(int i=0; i<N-1; i++){
                for(int j=0; j<M-1; j++){
                    char x = map[i][j];
                    if(x!='.'&&x==map[i][j+1]&&x==map[i+1][j]&&x==map[i+1][j+1]){
                        remove.add(i+" "+j);
                    }
                }
            }
            //삭제 로직
            for(String rm : remove){
                StringTokenizer st = new StringTokenizer(rm);
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                map[x][y]='.';
                map[x+1][y]='.';
                map[x][y+1]='.';
                map[x+1][y+1]='.';
            }
            // 빈칸 줄이기 로직
            for(int j=0; j<M; j++){
                ArrayList<Character> temp = new ArrayList<>();
                for(int i=N-1; i>=0; i--){
                    if(map[i][j]!='.'){
                        temp.add(map[i][j]);
                    }
                    map[i][j]='.';
                }
                for(int i=0; i<temp.size(); i++){
                    map[N-i-1][j] = temp.get(i);
                }
            }
        }
        int total=0;
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(map[i][j]=='.'){
                    total++;
                }
            }
        }
        return total;
    }
}
// 2곱 2짜리 칸들이 삭제되고 나서 위의 알파벳들을 내려준다. 
// 지워줄 칸들을 remove HashSet<Node>에 넣어주고 마지막에 한꺼번에 삭제해주고 빈칸들을 줄여준다.
//빈칸을 지우는 방법은 이렇다 밑에서부터 남은 블럭들을
//ArrayList에 넣어주고 개수만큼 밑에서 순회하며 넣어준다.
//더이상 줄어드는 경우가 없을경우 return해준다.
//이번 동작으로 인해 삭제된 블록이 없다면? -> 조건으로 종료

30분이내에 성공하는건 성공했지만 마음에 드는 코드는 아닌듯 하다.