[백준][Java] 1992번 쿼드트리 (분할정복, 재귀)

생각을 좀 많이함..

결국 (0000) (1111) 둘 중 하나가 만들어질 때 각각 0, 1로 대체할 수 있으면 되는데,

가장 작은 단위의 (0000) (1111)은 Line:29의 if(N==2)문에서 처리가 되지만

여기서 압축된 후에 생기게 되는 좀 더 큰 단위의 (0000) (1111) 들은 어떻게 처리해야 할까?

계속 while문으로 돌려야되나? 생각하다가

Line:47에다가 Line:35의 checkCanComp() 메소드 사용하면 되는 것을 깨달았다

 

결국은.. 소괄호로 닫아줄 때 -> ) 로 닫아줄 때 그 res.substring(res.length()-6, res.length())가

(0000)이거나 (1111)일 경우 각각 0과 1로 교체시켜주면

재귀로 처리하기 때문에 가장 작은 단위의 비디오 배열부터 처리가 되기 때문에

문제에서 요구하는 쿼드트리 결과가 나오게 됨..

 

뭔가 말로 설명하려니까 꼬이네

솔직히 ide로 하니까 진짜 할만한데

ide 못 쓰는 코테에서 프로그래머스 그 깡통에서 쌩으로 풀라고 하면 너무 힘들 것 같다..ㅠㅠ

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
 
public class Main {
    
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
    private static int[][] video;
    private static StringBuilder res;
    
    private static void checkCanComp() {
        String temp = res.substring(res.length()-6 ,res.length());
        if(temp.equals("(0000)")) {
            res.delete(res.length()-6 ,res.length());
            res.append("0");
        }
        else if(temp.equals("(1111)")) {
            res.delete(res.length()-6 ,res.length());
            res.append("1");
        }
    }
    
    private static void quadTree(int x, int y, int N) throws IOException{
        if(N==2) {
            res.append("(");
            for(int i=x; i<x+2; i++) 
                for(int j=y; j<y+2; j++) 
                    res.append(String.valueOf(video[i][j]));
            res.append(")");
            checkCanComp();
            return ;
        }
        
        N/=2;
        res.append("(");
        for(int i=0; i<2*N; i+=N) {
            for(int j=0; j<2*N; j+=N) {
                quadTree(x+i, y+j, N);
            }
        }
        res.append(")");
        checkCanComp();
    }
    
    public static void main(String[] args) throws IOException{
        // init
        int N = stoi(br.readLine());
        video = new int[N][N];
        res = new StringBuilder();
        for(int i=0; i<N; i++) {
            char[] input = br.readLine().toCharArray();
            for (int j=0; j<N; j++) 
                video[i][j] = input[j]-'0';
        }
        
        quadTree(0, 0, N);
        
        bw.write(res.toString());
        bw.flush();
        bw.close();
    }
    
 
    private static int stoi(String input) {
        return Integer.parseInt(input);
    }
}