프로그래머스(Java) - [1차] 프렌즈4블록

문제 링크

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

문제 풀이

Node 클래스의 i,j값은 2차원 배열에서 [i][j]값과 같다.
추후에 정렬을 할경우 i 값이 같다면 j에 대해서 내림차순으로 정렬되도록 설정하였다.
(내가 구현한 로직상 arraylist에서 값을 remove 하게 되는데 오름차순으로 정렬되면 순서가 당겨지는 경우가 생겨서 이를 막히위해 내림차순 정렬을 사용)

class Node implements Comparable<Node>{
    int i;
    int j;
    public Node(int i, int j){
        this.i=i;
        this.j=j;   
    }
 
    public int compareTo(Node o){
        if(i==o.i){
            return o.j-j;
        }else{
            return i-o.i;
        }
    }
}

TTTANT
RRFACC
RRRFCC
TRRRAA
TTMMMF
TMMTTJ
와 같은 모양에 대해서 세로로 구현하기 어려울 것으로 판단...
이것을 가로로 시계방향으로 눕히고, 블록들을 없애고, 왼쪽으로 땡겨주면 블록들이 내려가는것과 같은 로직일것이라 생각했다.

TTTRRT
MTRRRT
MMRRFT
TMRFAA
TMACCN
JFACCT
로 바뀐다.
아래 코드를 통해서 위와 같은 형태로 변경

        List<String> [] arr = new ArrayList[n];
        for(int i=0; i<arr.length;i++){
            arr[i] = new ArrayList();
         }
         for(int i=0; i<arr.length;i++){
            for(int j=board.length-1; j>=0; j--){
                arr[i].add(board[j].split("")[i]);
            }
        }

그리고 블럭들이 없더진다면

(1차 삭제)
TTTT
MTT
MMFT
TMRF
TMAN
JFAT
와 같이 바뀐다.

chk가 true인 동안에는 아직 제거할 블록들이 남았다는 뜻이다.
arr[] 에 대해서 2중 for문을 돈다.
현재 위치를 기준으로 오른쪽, 아래, 우측 대각선에 있는 3개의 칸들을 비교해서 모두 다 같은 값인지 체크한다. (단 -1은 빈칸이라는 뜻이므로 not 조건을 걸어준다.)
또한 맨 마지막 arr, 맨 마지막 list의 값은 확인할 필요가 없다!
만약에 arr[i].get(j) 에 대해서 if문의 조건들이 다 성립한다면
map에 4개의 값을 다 넣어준다.(중복된 타일이 들어올 수 있기에 map을 사용)

for(int i=0; i<arr.length-1; i++){ //맨 마지막 열은 따로 안해도 됨
	for(int j=0; j<arr[i].size()-1; j++){ //맨 마지막은 확인할 필요 없음
                if( arr[i].get(j).equals(arr[i].get(j+1)) &&
                    arr[i].get(j).equals(arr[i+1].get(j)) &&
                    arr[i].get(j).equals(arr[i+1].get(j+1)) &&
                    !arr[i].get(j).equals("-1")
                  ){ 
                    map.put(i+","+j,0);
                    map.put((i+1)+","+j,0);
                    map.put(i+","+(j+1),0);
                    map.put((i+1)+","+(j+1),0);
                }
            }
        }

위치 값을 나타내는 Node를 Type으로 가지는 nodelist를 선언
map에 담긴 위치값들을 parsing해서 nodelist에 넣어주고 compareTo에서 정한 방식대로 정렬하고 i번째 arr에 있는 list중에 j번째 값을 제거 그리고 맨 뒤에서부터 -1 값을 넣어준다. (배열의 크기를 일정하게 맞추기 위함)

        List<Node> nodelist = new ArrayList();
        for(Map.Entry<String,Integer> entry : map.entrySet()){
            int i = Integer.valueOf(entry.getKey().split(",")[0]);
            int j = Integer.valueOf(entry.getKey().split(",")[1]);
            // arr[i].remove(j);
            nodelist.add(new Node(i,j));
        }
        Collections.sort(nodelist);
        for(int k=0; k<nodelist.size(); k++){
            int i = nodelist.get(k).i;
            int j = nodelist.get(k).j;            
            arr[i].remove(j);
            arr[i].add("-1");
        }

이 과정을 계속해서 반복하는데
반복할때마다 answer에 이번 과정에서 제거될 타일의 개수인 map.size()를 더해준다.
만약 map의 크기가 0이라면 더이상 제거되는 타일이 없다는 뜻이므로
반복문을 탈출하도록 chk = false로 해준다.

   if(map.size()==0){
            chk = false;
        }  
        answer += map.size();

코드

import java.util.*;

class Node implements Comparable<Node>{
    int i;
    int j;
    public Node(int i, int j){
        this.i=i;
        this.j=j;   
    }
    
    public int compareTo(Node o){
        if(i==o.i){
            return o.j-j;
        }else{
            return i-o.i;
        }
    }
}

class Solution {
    public int solution(int m, int n, String[] board) {
        int answer = 0;
        List<String> [] arr = new ArrayList[n];
        
        for(int i=0; i<arr.length;i++){
            arr[i] = new ArrayList();
        }
        
         for(int i=0; i<arr.length;i++){
            for(int j=board.length-1; j>=0; j--){
                arr[i].add(board[j].split("")[i]);
            }
        }
        
//         for(int i=0; i<arr.length; i++){
//             System.out.println(arr[i]);
//         }
        
//         System.out.println("=============");
        
        boolean chk = true;
        while(chk){
        Map<String,Integer> map = new HashMap();
        for(int i=0; i<arr.length-1; i++){ //맨 마지막 열은 따로 안해도 됨

            for(int j=0; j<arr[i].size()-1; j++){ //맨 마지막은 확인할 필요 없음
                //System.out.print(arr[i].get(j));
                
                
                if( arr[i].get(j).equals(arr[i].get(j+1)) &&
                    arr[i].get(j).equals(arr[i+1].get(j)) &&
                    arr[i].get(j).equals(arr[i+1].get(j+1)) &&
                    !arr[i].get(j).equals("-1")
                  ){ 
                    map.put(i+","+j,0);
                    map.put((i+1)+","+j,0);
                    map.put(i+","+(j+1),0);
                    map.put((i+1)+","+(j+1),0);
                    
                }else{
                    
                }
            }
            //System.out.println("");
        }
        List<Node> nodelist = new ArrayList();
        for(Map.Entry<String,Integer> entry : map.entrySet()){
            int i = Integer.valueOf(entry.getKey().split(",")[0]);
            int j = Integer.valueOf(entry.getKey().split(",")[1]);
            // arr[i].remove(j);
            nodelist.add(new Node(i,j));
        }
        Collections.sort(nodelist);
        for(int k=0; k<nodelist.size(); k++){
            int i = nodelist.get(k).i;
            int j = nodelist.get(k).j;            
            arr[i].remove(j);
            arr[i].add("-1");
        }    

        // for(int i=0; i<arr.length; i++){
        //     System.out.println(arr[i]);
        // } 
            
            
        //System.out.println("=============");
        if(map.size()==0){
            chk = false;
        }  
        answer += map.size();
            
        }//while    
        //System.out.println(map.toString());
        
        return answer;
    }
}