[백준] Silver 1 쿼드트리

https://www.acmicpc.net/problem/1992

1992번: 쿼드트리

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static StringBuilder sb = new StringBuilder();
    static int [][] board;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        board = new int[n][n];
        for(int i = 0; i < n; i++) {
            String input = br.readLine();
            for(int j = 0; j < n; j++){
                board[i][j] = input.charAt(j) - '0';
            }
        }
        compact(0,0, n);
        System.out.println(sb.toString());
    }

    private static void compact(int x, int y, int size) {
        if (check(x,y,size)) {
            sb.append(board[x][y]);
            return;
        }

        sb.append("(");
        int newLen = size / 2;
        compact(x, y, newLen);
        compact( x , y + newLen , newLen);
        compact(x + newLen, y , newLen);
        compact(x + newLen, y + newLen , newLen);
        sb.append(")");
    }

    private static boolean check(int x, int y, int size) {
        for(int i = x; i < x + size; i++){
            for(int j = y; j < y + size; j++) {
                if (board[x][y] != board[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }
}

 

풀이 회고

 

앞에서 풀었던 프로그래머스 문제랑 99퍼센트 일치하는 문제였다.

 

차이점이 있다면, 압축이 되었을 때 StringBuilder에 값을 더해주고 또 각 area를 구분하기 위해서 괄호를 더해주었다.