[BaekJoon/백준] 2447번

별찍기 문제다. 재귀를 이용한 별찍기 문제인데, 포문을 이용하면 정말 금방 끝날 문제일 것 같은데 문제에서 재귀함수를 이용하란다.

음.. 재귀로 이 문제를 풀기에는 당연히 제한시간 1초에 걸릴 거라고 생각해서 무조건 for문은 들어가겠다고 생각은 들었다.

 

for문을 통한 문제해결의 생각만 들다보니 아무래도 재귀와 for문을 짬뽕시켜 풀게되었다.

(JAVA)

import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.Scanner;

public class star_point {
    static int arr[][] = new int[2188][2188]; //문제의 제한인 3의7승 +1값(내 코드는 1,1부터 시작하므로)
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = scanner.nextInt();
        print_star(1, 1,N);
        
        try {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (arr[i][j] == 0)
                        bw.write("*");
                    else
                        bw.write(" ");
                }
                bw.write("\n");
            }
            bw.flush(); bw.close();
        }catch (Exception e) {
        }
    }
   
    public static void print_star(int a, int b, int N) {
        for(int i =a; i<N+a ; i=i+N/3) {
            for(int j=b; j<N+b; j=j+N/3) {
                if((i==(a+N/3))&&(j==(b+N/3))) {
                    for(int x=0; x<N/3;x++) {
                        for(int y=0; y<N/3;y++)
                            arr[i+x][j+y]=1;
                    }
                } else if(N/3!=1)
                    print_star(i, j, N/3);
            }
        }
    }
}

포문으로만 이용하면 쉽게풀거같은데, 재귀를 이용하라길래.. 좀어려웠다. 결국 포문 위주로 풀긴했지만 재귀와 짬뽕했다..

 

내 방식은 문제를 배열로 풀어나간다. 문제에서 공백을 표현할 곳을 찾아내서 배열 값을 1로 처리해놓은 뒤

나중에 포문을 돌며 1인 곳은 공백, 아닌 곳은 별로 출력시키는 방식이다.

 

코드나 시간복잡도가 깔끔하거나 효율적이진 않다.. 그래서 문제를 해결한 뒤에 다른 분들의 코드를 참고해봤다.

 

아래 코드는 고수분의 코드를 참조했다.

(C++)

#include <stdio.h>
#include <string.h>
 
char mat[2201][2201];
 
void solve(int y, int x, int num)
{
    if(num == 1)
    {
        mat[y][x]='*';
        return;
    }
     
    int div = num/3;
    for(int i=0; i<3; i++)
    {
        for(int j=0; j<3; j++)
        {
            if(i == 1 && j == 1)
                ;
            else
                solve(y+(i*div), x+(j*div), div);
        }
    }
}
int main()
{
    int n;
    scanf("%d", &n);
     
    memset(mat, ' ', sizeof(mat));
     
    solve(0, 0, n);
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
            printf("%c", mat[i][j]);
        printf("\n");
    }
    
    return 0;
}

내 코드보다 더 재귀스럽고, 덜 복잡하며 깔끔한 코드다. 그리고 이분께서는 공백처리할 곳을 처리하기보다 별을 출력할 곳을 처리한 방식으로 내 코드와는 조금 다르다. 전체적으로 깔끔해서 본받을 점이 많다.

 

정말 '재귀' 라는 표현에 맞게, 포문을 덜 이용하셨고 처리할 부분이 3x3이던 9x9이던 27x27이던 간에 3x3 방식으로 묶어서 생각하여 처리하셨다. 물론 나도 묶어서 처리하긴 했으나, 포문 헤드의 연산 처리나 이런 부분이 묶어서 처리했다고 하기가 애매할 정도로 복잡하다. 이분은 재귀함수를 호출하는 부분에 연산처리를 해놓으셨지만 나는 포문에다가 연산처리를 해놓아서 보기가 그렇게 좋진 않다. 전자가 조금 더 재귀함수스러운 방식인 것 같다.

 

공백을 처리하냐 별을 처리하냐는 나와 완전히 다른 방식이지만, 공백 위치와 별 위치를 찾는 방식은 나와 같다. 근데 이분의 코드가 훨씬 깔끔하다.

실질적인 방향성은 같은데, 코드가 더 지저분하고 속도가 느리다는 것은 내가 리팩토링을 너무 못했다는 것..

성찰해야겠다.

 

 

이에, 리팩토링 연습 1

import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Scanner;

public class star_point {
    static char arr[][];

    public static void main(String args[]) throws Exception {
        Scanner scanner = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = scanner.nextInt();
        arr = new char[N+1][N+1];
        for(char[] ch : arr)
            Arrays.fill(ch, '*');
        print_star(1, 1, N);
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                bw.write(arr[i][j]);
            }
            bw.write("\n");
        }
        bw.flush();
        bw.close();
    }
    public static void print_star(int a, int b, int N) {

        int div = N/3;
        for (int i=a;i<N+a;i=i+div) {
            for (int j=b;j<N+b;j=j+div) {
                if ((i==(a+div))&&(j==(b+div))) {
                    for (int x=0;x<div;x++) {
                        for (int y=0;y<div; y++) {
                            arr[i+x][j+y] = ' ';
                        }
                    }
                } else if (div!=1)
                    print_star(i,j,div);
            }
        }
    }
}

try ~ catch()를 함수로 throw 시켰고, 배열 할당을 동적으로 변경하였으며

1을 채워서 나중에 이를 공백으로 바꾸는 처리 대신에 곧바로 별과 공백을 구분함.

 

하지만 여전히 '별'을 채우는 방식보다 '공백'을 채우는 방식을 사용중이고, 여전히 덜 재귀스러운 코드와 느린 실행 시간이 문제.

 

리펙토링 연습 2-1

import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Scanner;

public class star_point {
    static char arr[][];

    public static void main(String args[]) throws Exception {
        Scanner scanner = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = scanner.nextInt();
        arr = new char[N][N];
        for(char[] ch : arr)
            Arrays.fill(ch, ' ');
        print_star(0, 0, N);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                bw.write(arr[i][j]);
            }
            bw.write("\n");
        }
        bw.flush();
        bw.close();
    }
    
    // a와 b가 작업을 시작할 기준점 역할. 모든 것을 3x3으로 묶어서 생각하고, 실제 기준점을 a와 b로 보완해줌. 
    public static void print_star(int a, int b, int N) {
        int div = N/3;
        for (int i=0;i<3;i++) {
            for (int j=0;j<3;j++) {
                if ((i==1)&&(j==1))
                    continue;
                else if (div!=1)
                    print_star(a+(i*div),b+(j*div),div);
                else
                    arr[a+(i*div)][b+(j*div)]='*';
            }
        }
    }
}

아예 재귀스럽게 바꿔봤음. 기존에 공백을 기준으로 처리하는 대신에 이번엔 별을 기준으로 처리하도록 완전히 변경했음.

 

리펙토링 연습 2-2

import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Scanner;

public class star_point {
    static char arr[][];

    public static void main(String args[]) throws Exception {
        Scanner scanner = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = scanner.nextInt();
        arr = new char[N][N];
        for(char[] ch : arr)
            Arrays.fill(ch, ' ');
        print_star(0, 0, N);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                bw.write(arr[i][j]);
            }
            bw.write("\n");
        }
        bw.flush();
        bw.close();
    }

    // a와 b가 작업을 시작할 기준점 역할. 모든 것을 3x3으로 묶어서 생각하고, 실제 기준점을 a와 b로 보완해줌.
    public static void print_star(int a, int b, int N) {
        if(N==1) {
            arr[a][b] = '*';
            return;
        }
        int div = N/3;
        for (int i=0;i<3;i++) {
            for (int j=0;j<3;j++) {
                if ((i==1)&&(j==1))
                    continue;
                else
                    print_star(a+(i*div),b+(j*div),div);
            }
        }
    }
}

기존 else 문 대신에 if(N==1)을 정의시켜서 조금 더 재귀스럽게 바꿔봤음.