[백준] 단계별로 풀어보기 > 재귀 (Java)

+) 풀이 코드

https://github.com/jung0115/CodingTestPractice.git

GitHub - jung0115/CodingTestPractice: Practice Coding Test with Beakjoon, programmers, etc.

 

+) 백준에 Java 코드를 제출할 때는 class명을 Main으로 해주어야 오류가 발생하지 않는다.

 

10872번 - 2022.01.09.일

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        int N;
        Scanner scan = new Scanner(System.in);
        N = scan.nextInt();
        scan.close();

        int fac;
        fac = factorial(N);

        System.out.println(fac);
    }
    static int factorial(int n) {
        if(n == 0 || n == 1) return 1;
        return factorial(n-1) * n;
    }
}

 

10870번 - 2022.01.10.월

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        int n;
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        scan.close();
        
        int fibo_result;
        fibo_result = fibo(n);
        System.out.println(fibo_result);
    }
    static int fibo(int num) {
        if(num == 0 || num == 1) return num;
        return fibo(num-1) + fibo(num-2);
    }
}

 

2447번 - 2022.01.10.월 (Time Limited)

import java.util.Scanner;
public class Main{
    static String[][] starCheck = new String[6561][6561];
    public static void main(String[] args) {
        int N;
        Scanner scan = new Scanner(System.in);
        N = scan.nextInt();
        scan.close();
        starSquare(N, 0, 0, "*");

        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++)
                System.out.print(starCheck[i][j]);
            System.out.println("");
        }
    }
    static void starSquare(int N, int x, int y, String star){
        if(N == 1) starCheck[x][y] = star;
        else if(star == " ") {
            starSquare(N/3, x, y, " ");
            starSquare(N/3, x+(N/3), y, " ");
            starSquare(N/3, x+2*(N/3), y, " ");
            starSquare(N/3, x, y+(N/3), " ");
            starSquare(N/3, x+(N/3), y+(N/3), " ");
            starSquare(N/3, x+2*(N/3), y+(N/3), " ");
            starSquare(N/3, x, y+2*(N/3), " ");
            starSquare(N/3, x+(N/3), y+2*(N/3), " ");
            starSquare(N/3, x+2*(N/3), y+2*(N/3), " ");
        }
        else{
            //***
            starSquare(N/3, x, y, "*");
            starSquare(N/3, x+(N/3), y, "*");
            starSquare(N/3, x+2*(N/3), y, "*");
            //* *
            starSquare(N/3, x, y+(N/3), "*");
            starSquare(N/3, x+(N/3), y+(N/3), " ");
            starSquare(N/3, x+2*(N/3), y+(N/3), "*");
            //***
            starSquare(N/3, x, y+2*(N/3), "*");
            starSquare(N/3, x+(N/3), y+2*(N/3), "*");
            starSquare(N/3, x+2*(N/3), y+2*(N/3), "*");
        }
    }
}

모양은 제대로 나오는데 시간이 너무 오래 걸린다. 어떻게 하면 시간을 단축시킬까...

Scanner로 풀면 System.out.print로 출력할 때 시간 초과가 발생한다고 한다... 때문에 StringBuilder, BufferedWriter 중 하나를 사용해야 한다.

 

2447번 - 2022.01.10.월 (해결)

import java.util.Scanner;
public class Main {
    static String[][] starCheck;
    public static void main(String[] args) {
        int N;
        Scanner scan = new Scanner(System.in);
        N = scan.nextInt();
        scan.close();

        starCheck = new String[N][N];

        starSquare(N, 0, 0, true);

        StringBuilder printSet = new StringBuilder();
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++)
                printSet.append(starCheck[i][j]);
            printSet.append("\n");
        }
        System.out.print(printSet);
    }
    static void starSquare(int N, int x, int y, boolean star){
        if(!star) {
            for(int i = x; i < x+N; i++) {
                for(int j = y; j < y+N; j++) {
                    starCheck[i][j] = " ";
                }
            }
            return;
        }
        if(N == 1) {
            starCheck[x][y] = "*";
            return;
        }

        for(int i = 0; i < 3; i++) {
            for(int j = 0; j < 3; j++) {
                if(i == 1 && j == 1) starSquare(N/3, x + i*(N/3), y + j*(N/3), false);
                else starSquare(N/3, x + i*(N/3), y + j*(N/3), true);
            }
        }
    }
}

시간 초과를 해결하기 위해 StringBuilder를 사용하면서 코드를 간결(?)하게 정리해주었다.

 

11729번 - 2022.01.11.화

import java.util.Scanner;
public class Main {
    static StringBuilder move = new StringBuilder();
    public static void main(String[] args) {
        int N;
        Scanner scan = new Scanner(System.in);
        N = scan.nextInt();
        scan.close();

        int cnt;
        cnt = hanoi(1, 2, 3, N);
        System.out.println(cnt);
        System.out.print(move);
    }
    static int hanoi(int start, int middle, int finish, int N) {
        if(N == 1) {
            move.append(start + " " + finish + "\n");
            return 1;
        }
        int cnt = 0;
        cnt += hanoi(start, finish, middle, N-1);
        move.append(start + " " + finish + "\n"); cnt++;
        cnt += hanoi(middle, start, finish, N-1);

        return cnt;
    }
}

이동 과정을 따로 저장하지 않고 hanoi 함수 안에서 출력까지 다 하고 싶었는데 그러면 총 이동 횟수를 먼저 출력하는 것이 불가능해진다. 방법을 열심히 생각해봤지만 결국 찾지 못해 따로 저장 후 한 번에 출력하는 방식을 사용했다.