[알고리즘_풀이] 카카오코딩테스트, 프렌즈 4블록(java)

코드 설명

변수/객체

boardC : 입력받은 배열 board를 char배열로 잘라서 char[][] 에 넣음

marked :  한번 루프를 돌 때, 2x2블록이 완성되면 true. 완성된 블록의 개수를 셀 때도 사용됌.

finalFlag : 더 이상 2x2블록이 없을 때, finalFlag는 false가 되어 최종 루프를 빠져나가기 위해 사용됌.

 

메서드

 (-> 메서드에 m, n을 넣은 이유는 전역변수로 선언을 하기 번거롭기 때문.)

1 .checkBlock(int m, int n) 

 2x2가 있는 블록을 체크하고 블록이 완성되면 해당하는 인덱스에 marked[i][j] = true로 표시.

 

2. processBlock(int m, int n) - > int로 반환

 marked값을 보고 true인 것은 제거해야할 대상이다. 제거될 블록을 count하면서(marked[i][j] == true이면 count++ ) 해당하는 boardC에 공백을 넣는다.

 

3. rearrangeBoard(int m, int n)

 열을 기준으로 가져와서 tmpStr에 하나씩 넣는다. 이 후, 공백을 제외해서 다시 담고 boardC의 한 열의 맨 뒤 인덱스부터 tmpStr의 크기만큼 charAt()을 통해서 넣는다. 만약 넣어야할 문자의 크기(tmpStr)가 열의 전체 크기보다 작다면 채우고 난 후 공백을 채워야하기때문에 그만큼 채워주는 코드를 넣는다.

 

-> 이 것을 checkBlock에서 아무것도 만들어진 블록이 없을 때, 다시말해서 !finalFlag 이거인 경우 루프를 빠져나간다.

 

 

 

 

프로그래머스용 코드

class Solution {
    //boardC와 marked를 전역변수로 선언
    static char[][] boardC = null;
    static boolean[][] marked = null;
    static boolean finalFlag = true;

    static void checkBlock(int m, int n){
   	//dx, dy : 자신을 기준으로 오른쪽, 아래, 그리고 대각선. 즉, 자신을 포함해서 2x2가 되는 원소를 체크하기 위함.
        int[] dx = {0, 1, 1};
        int[] dy = {1, 0, 1};

        for(int i=0; i<m-1; i++) {
            for (int j = 0; j <n-1; j++) {
                //내가 타탕한지 판단, 공백이 아니어야한다.
                if(boardC[i][j] == ' '){
                    continue;
                }
                boolean flag = false;
                for(int k=0; k<3; k++){
                    int x = i + dy[k];
                    int y = j + dx[k];
                    if(x>=0 && y>=0 && x<m && y<n){
                        //하나라도 틀리면 flag는 true
                        if(boardC[i][j] != boardC[x][y]){
                            flag = true;
                            break;
                        }
                    }
                }

                //한블록이 완성되면 flag는 false
                if(!flag){
                    finalFlag = true;
                    //자기자신, 그리고 한 블록이 된 멤버들 모두 marked를 true로 만들어주기
                    marked[i][j] = true;
                    for(int k=0; k<3; k++){
                        int mx = i+dx[k];
                        int my = j+dy[k];
                        marked[mx][my] = true;
                    }
                }
            }
        }
    }

    // marked[i][j] == true인 것을 세고, 그 자리에 boardC[i][j] = ' '로 공백 처리, count로 리턴
    static int processBlock(int m, int n){
        int count = 0;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(marked[i][j]){
                    boardC[i][j] = ' ';
                    count += 1;
                }
            }
        }
        return count;
    }

    //공백인 것들을 열기준으로 아래로 밀기. 그에 따라 marked도 다시
    static void rearrangeBlock(int m, int n){
        //중요한 점은 열 단위로 봐야함. 공백이 있으면 아래로 내려가야하기 때문!
        String tmpStr = "";
        for(int j=0; j<n; j++){
            tmpStr = "";
            //j열에 해당하는 값을 모으기 위한 loop
            for(int i=0; i<m; i++){
                tmpStr += boardC[i][j];
            }
            //공백이 있으면 제거하고
            tmpStr = tmpStr.replaceAll(" ", "");

            //뒤에서부터 tmpStr.charAt을 사용해서 하나씩 다시 넣는다.
            for(int i=0; i<tmpStr.length(); i++){
                boardC[m-1-i][j] = tmpStr.charAt(tmpStr.length()-1-i);
                marked[m-1-i][j] = false;
            }

            if(m > tmpStr.length()){
                int loop = m-tmpStr.length();
                for(int i=loop-1; i>=0; i--){
                    boardC[i][j] = ' ';
                    marked[i][j] = false;
                }
            }
        }
    }

    public static int solution(int m, int n, String[] board) {
        int answer = 0;

        boardC = new char[m][n];
        marked = new boolean[m][n];
        //board를 입력 받는다.
        for(int i=0; i<m; i++){
            boardC[i] = board[i].toCharArray();
        }


        while(finalFlag){
            finalFlag = false;
            checkBlock(m, n);
            answer += processBlock(m, n);
            rearrangeBlock(m, n);
        }

        return answer;
    }
}

 

IDE용 코드

package codingTest;

public class kakao_friendsBlock {
    //boardC와 marked를 전역변수로 선언
    static char[][] boardC = null;
    static boolean[][] marked = null;
    static boolean finalFlag = true;

    static void checkBlock(int m, int n){
        int[] dx = {0, 1, 1};
        int[] dy = {1, 0, 1};

        for(int i=0; i<m-1; i++) {
            for (int j = 0; j <n-1; j++) {
                //내가 타탕한지 판단, 공백이 아니어야한다.
                if(boardC[i][j] == ' '){
                    continue;
                }
                boolean flag = false;
                for(int k=0; k<3; k++){
                    int x = i + dy[k];
                    int y = j + dx[k];
                    if(x>=0 && y>=0 && x<m && y<n){
                        //하나라도 틀리면 flag는 true
                        if(boardC[i][j] != boardC[x][y]){
                            flag = true;
                            break;
                        }
                    }
                }

                //한블록이 완성되면 flag는 false
                if(!flag){
                    finalFlag = true;
                    //자기자신, 그리고 한 블록이 된 멤버들 모두 marked를 true로 만들어주기
                    marked[i][j] = true;
                    for(int k=0; k<3; k++){
                        int mx = i+dx[k];
                        int my = j+dy[k];
                        marked[mx][my] = true;
                    }
                }
            }
        }
    }

    // marked[i][j] == true인 것을 세고, 그 자리에 boardC[i][j] = ' '로 공백 처리, count로 리턴
    static int processBlock(int m, int n){
        int count = 0;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(marked[i][j]){
                    boardC[i][j] = ' ';
                    count += 1;
                }
            }
        }
        return count;
    }

    //공백인 것들을 열기준으로 아래로 밀기. 그에 따라 marked도 다시
    static void rearrangeBlock(int m, int n){
        //중요한 점은 열 단위로 봐야함. 공백이 있으면 아래로 내려가야하기 때문!
        String tmpStr = "";
        for(int j=0; j<n; j++){
            tmpStr = "";
            //j열에 해당하는 값을 모으기 위한 loop
            for(int i=0; i<m; i++){
                tmpStr += boardC[i][j];
            }
            //공백이 있으면 제거하고
            tmpStr = tmpStr.replaceAll(" ", "");

            //뒤에서부터 tmpStr.charAt을 사용해서 하나씩 다시 넣는다.
            for(int i=0; i<tmpStr.length(); i++){
                boardC[m-1-i][j] = tmpStr.charAt(tmpStr.length()-1-i);
                marked[m-1-i][j] = false;
            }

            if(m > tmpStr.length()){
                int loop = m-tmpStr.length();
                for(int i=loop-1; i>=0; i--){
                    boardC[i][j] = ' ';
                    marked[i][j] = false;
                }
            }

        }

        //System.out.println(tmpStr);
    }

    static void printBoardC(){
        for(char[] ci : boardC){
            for(char cj : ci){
                System.out.print(cj + " ");
            }
            System.out.println();
        }
    }

    static void printMarked(){
        for(boolean[] mi : marked){
            for(boolean mj : mi){
                System.out.print(mj + " ");
            }
            System.out.println();
        }
    }

    public static int solution(int m, int n, String[] board) {
        int answer = 0;

        boardC = new char[m][n];
        marked = new boolean[m][n];
        //board를 입력 받는다.
        for(int i=0; i<m; i++){
            boardC[i] = board[i].toCharArray();
        }


        while(finalFlag){
            finalFlag = false;
            checkBlock(m, n);
            answer += processBlock(m, n);
            rearrangeBlock(m, n);
        }

        printBoardC();
        printMarked();


        return answer;
    }

    public static void main(String[] args) {
        String[] board = {"CCBDE", "AAADE", "AAABF", "CCBBF"};
        System.out.println(solution(4, 5, board));
    }
}

 

 

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

코딩테스트 연습 - [1차] 프렌즈4블록 | 프로그래머스