[Dev-Ping9] 백준 2447번 - 별 찍기 - 10 (Java) [DP]

하하하하하핳하하하 풀었다 이 말이야 하하하하하하!!!! 😘

 

 

 

# 문제 설명

• 입력은 3^1 에서 3^7까지 이다.

 

[작은 사각형부터 k=1, k=2, k=3]

 

 

# 규칙 찾기

• k=1 인 사각형을 만들 수 있다면, k=2 를 만들때 k=1을 사용하면 될 것 같은 느낌이다.

 

즉, k=1인 사각형을 dp[1]이라 부른다면, dp[2]는 8개의 dp[1] + 중앙이 빈 형태이다.

k=n 일때의 사각형을 만들려면, k=n-1 사각형의 크기가 9개가 필요하다...!

그리고 9개 중, 5번째 사각형은 공백이어야한다. 

 

• String으로 저 로직을 처리하려면, 개행문자 때문에 상당히 복잡하다. (한번 해봤다가 피봤다...)
• 그리고 이전의 부분구조가 다음의 부분구조에 쓰이므로 DP문제임이 암시되기에, 배열로 선언하고 사용하는게 훨씬 편하다.
• k=0을 1x1 배열인 [ '*' ] 로 두고, k=0 부터 풀어가도 괜찮다.
• 필자는 문제에 '재귀적인 패턴으로 별을 찍어보자' 에 꽂혀 DP를 떠올리는데 오랜시간이 걸렸는데, 재귀호출은 구현기법일 뿐, 문제해결(알고리즘) 방법에는 포함되지 않는다는 것을 명심해두자..!

 

 

# 코드 구현

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main{
    
    static void drawStar2(int k, int target){// k=2~7
        //메모리는 하나만 참조하도록! 전역변수 배열을 dp로 둔다..! 
        int previousN = (int)Math.pow(3,k-1); //previous index;
        
        //section 은 항상 3x3 (1~9)
        //section 5 는 항상 빈값
        //그외에 section 은 그 전 array를 copy
        int YStart = 0; int YEnd = previousN; //arr[i][j] 에서 j 를 y로 뒀다.
        int XStart = 0; int XEnd = previousN; //arr[i][j] 에서 i 를 x로 뒀다.
        int preX=0; int preY=0; //이전의 배열을 복사할 때 사용할 index이다.
        
        for(int section=0; section<9; section++){ // copy section 1~9
            if(section%3==0 && section!=0){ //1~3 까지 채우고, 4~6번 사각형을 채울 때 x의 위치는 내려간다.
                YStart=0; YEnd=previousN;
                XStart+=previousN; XEnd+=previousN;
            }

            for(int x=XStart; x<XEnd; x++){
                // 공백으로 안채워넣으면 출력시 ' '가 아닌 ''로 출력됨 (즉, 출력이 아무것도 안됨)
                // if(section ==4 ) break; 
                
                for(int y=YStart; y<YEnd; y++){
                    if(section!=4){
                        dp[x][y] = dp[preX][preY++];
                    }else{
                        dp[x][y] = ' ';
                    }
                }
                preY=0;
                preX++;
            }
            YStart+=previousN;
            YEnd+=previousN;
            preX=0;
            preY=0;
        }
        if(k == target) return; 
        drawStar2(k+1, target);
    }

    static void printArr2(char[][] arr) throws IOException{
    	// 3^7 일 경우, 출력문이 엄청나기에 BufferedWriter 를 사용하는 것이 수행시간 단축에 긍정적인 영향을 준다.
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i=0; i<arr.length; i++){
            bw.write(arr[i]); // c언어와 똑같이 자바도 char[] 을 string으로 취급하나보다..!
            bw.write("\n");
        }
        bw.flush();
        bw.close();
    }

    static char[][] dp; // 사용할 전역배열

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        //n < 3^8
        int n = Integer.parseInt(br.readLine());
            
        int target = (int)Math.log(n); // input인 n을 3^k로 표현할때의 k이다.
        dp = new char[n][n];
        for(int i=0;i<3;i++){ // init dp[1]
            for(int j=0;j<3;j++){
                dp[i][j]='*';
            }
        }
        dp[1][1]=' ';
        
        //minimum input handling
        if(n==3){ // k==1 일때 조건문을 걸었다. dp[0]부터 시작한다면 필요없는 조건문이다.
            printArr2(dp);
            return;
        }

        drawStar2(2, target); //drawStar2는 (2, target) -> (target,target) 까지 호출된다.

        printArr2(dp);        
    }
}

 

---

 

# 코드 리뷰 및 이번 문제 풀이를 하며 배운 점

(필자의 일기장입니다...)

 

 

1. Java에서의 메모리해제 (참조블로그)

Item 7. 다 쓴 객체는 참조를 해제하라 | Carrey`s 기술블로그

 

2. 재귀호출로 reference variable(참조변수)을 계속 매개변수로 넘겨주면, 당연히 마지막 호출이 끝날때까지 모든 참조변수는 메모리 위에 살아있다.

(다음단계 호출에서 사용하고 난 후 해제할 방법을 한참 고민하였으나, 불가능하다 결론내렸다.)

(단순히 주소를 copy 받아서 오니, 배열의 값을 다 사용하고, 해당주소에 직접접근하여 메모리해제를 하는 방법이 있다면 가능할 듯)

     /* 이 친구는 2차원 배열을 리턴하고, 2차원배열을 매개변수로 받는다.
     * 메모리 낭비가 엄청나다. 인풋값이 3^7 까지 밖에안되서, 몇개안쓰는데 터지겠어? 했다가 터졌다. */
     static char[][] drawStar(int k, char[][] previousArray, int target){//2부터 ~ 8까지 
        
        int previousN = (int)Math.pow(3,k-1);
        int N = (int)Math.pow(3,k);
        char[][] nowArray = new char[N][N];
        
        int YStart = 0; int XStart = 0;
        int YEnd = previousN; int XEnd = previousN;
        int preX=0; int preY=0;
        for(int section=0; section<9; section++){ // copy section 1~9
            if(section%3==0 && section!=0){
                YStart=0; YEnd=previousN;
                XStart+=previousN; XEnd+=previousN;
            }
            for(int x=XStart;x<XEnd;x++){
                // if(section ==4 ) break; 공백으로 안채워넣으면 출력시 ' '가 아닌 ''로 출력됨
                for(int y=YStart;y<YEnd;y++){
                    if(section!=4){
                        nowArray[x][y] = previousArray[preX][preY++];
                    }else{
                        nowArray[x][y] = ' ';
                    }
                }
                preY=0;
                preX++;
            }
            YStart+=previousN;
            YEnd+=previousN;
            preX=0;
            preY=0;
        }
        if(k == target) return nowArray;
        previousArray=null; // nowArray 메모리해제 ...... 어케 해 ...흑흑 
        return drawStar(k+1, nowArray, target);
    }

    /* 이쁘게 메모리를 하나만 쓰도록 변경했다. */
    static void drawStar2(int k, int target){//2부터 ~ 8까지 
        //메모리는 하나만 참조하도록! 전역변수를 설정!
        int previousN = (int)Math.pow(3,k-1); //previous index;
        
        //copy logic is same.
        int YStart = 0; int XStart = 0;
        int YEnd = previousN; int XEnd = previousN;
        int preX=0;
        int preY=0;
        for(int section=0; section<9; section++){ // copy section 1~9
            if(section%3==0 && section!=0){
                YStart=0; YEnd=previousN;
                XStart+=previousN; XEnd+=previousN;
            }

            for(int x=XStart;x<XEnd;x++){
                // if(section ==4 ) break; 공백으로 안채워넣으면 출력시 ' '가 아닌 ''로 출력됨
                for(int y=YStart;y<YEnd;y++){
                    if(section!=4){
                        ans[x][y] = ans[preX][preY++];
                    }else{
                        ans[x][y] = ' ';
                    }
                }
                preY=0;
                preX++;
            }
            YStart+=previousN;
            YEnd+=previousN;
            preX=0;
            preY=0;
        }
        if(k == target) return; 
        drawStar2(k+1, target);
    }

 

3.  C언어와 같이 Java 또한 char 배열의 주소를 받으면 String 처리하여 출력한다. (String 문제 핸들링 할 때 유용할 것 같다.)

    /* 두 함수 모두 같은 기능이다. */
    static void printArr1(char[][] arr){
        for(int i=0; i<arr.length; i++){
            // 주소값을 출력하는게 아닌 String으로 취급하여 출력한다.
            System.out.println(arr[i]);
        }
    }
    /* same function with printArr1 */
    static void printArr2(char[][] arr){
        for(int i=0; i<arr.length; i++){
            for(int j=0; j<arr[0].length; j++){
                System.out.print(arr[i][j]);
            }
            System.out.println();
        }
    }

 

4. BuffredWriter 를 선언하고 bw.close() 를 하면, sys.out.print 형제들 또한 작동하지 않는다.

(System.out 자체가 close 되는 듯.)