[백준][Java] 4779 칸토어 집합

문제

칸토어 집합

시간초과 오답 원인 1

재귀로 풀었지만 시간초과로 실패.
원인은 Math.pow()

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = 0;
        while(sc.hasNextInt()){
            n = sc.nextInt();
            recursion(n);
            System.out.println();
        }
    }
    public static void recursion(int n) {
        if(n == 0) {
            System.out.print("-");
            return ;
        }
        
        recursion(n-1);
        for(int i = 0; i < Math.pow(3, n)/3; i++) {
            System.out.print(" ");
        }
        recursion(n-1);
    }
}

시간초과 오답 원인 2

Math.pow() 연산은 double 연산, 즉 부동소수점 연산이라 느리다.
재귀횟수가 $2^{n+1}-1$ 이므로 Math.pow() 횟수도 $2^{n+1}-1$ 이 된다.
Math.pow() 를 최초 한번만 수행하고 정수로 저장, 그 이후로 정수 나눗셈을 수행하도록 수정했다.
하지만 마찬가지로 시간초과 발생했다.
원인은 System.out.print()

메모리 초과

System.out.print() 가 문제인걸 알았다.
System.out.println 과 print 는 사용할 때 마다 flush(+ I/O) 가 발생한다.
찾아보니 이것 말고도 syncronized 로 인한 오버헤드도 생긴다고한다.
아무튼 System.out.print 은 많이 사용하면 시간초과가 발생하기 때문에 문자열 덧셈으로 수정했더니 시간초과가 해결되고 메모리초과가 발생했다.

public static void recursion2(int n, int len) {
        if(n == 0) {
            // System.out.print("-");
            rst += "-"; // <-- 메모리초과 발생
            return ;
        }
        
        recursion2(n-1, len/3);
        for(int i = 0; i < len; i++) {
            //System.out.print(" ");
            rst += " "; // <-- 메모리초과 발생
        }
        recursion2(n-1, len/3);
    }

메모리 초과 오답 원인

java 의 String 은 불변객체라서 그렇다.
String 을 불변객체로 만든 이유와 이점은 검색하면 아주 쉽게 설명되어 있는 글이 많다.
여기서는 메모리 초과가 발생한 이유만 설명한다.
처음엔 rst 는 “” 를 가리킨다.
그 다음 rst += “-“ ; 를 만나면서 String constant pool 에는 “-“ 문자열이 새로 생기고 rst 는 그 문자열을 가리킨다.
그 다음 rst += “ “ ; 를 만나면서 String constant pool 에는 “- “ 라는 문자열이 새로 생기고 rst 는 그 문자열을 가리킨다.
… 반복하게 되면 문자열이 $2^{n+1}-1$ 개 생기므로 메모리 초과가 발생한다.

정답

String 대신 사용할 수 있는건 StringBuilder 와 StringBuffer 가 있는데, 여기서는 StringBuilder 를 사용한다.
StringBuilder 와 StringBuffer 의 차이는 검색하면 잘 설명된 글이 많으니 모르면 한번은 읽어보는게 좋다.
String rst = ""; 를 StringBuilder rst = new StringBuilder();로 고쳤다.

import java.util.Scanner;
public class Main {
    public static StringBuilder rst = new StringBuilder();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = 0;
        int len = 0;
        while(sc.hasNextInt()){
            rst.setLength(0); // rst 초기화. 문자열로 비유하면 rst = "";
            n = sc.nextInt();
            len =(int)(Math.pow(3, n)/3);
            recursion(n, len);
            System.out.println(rst);
        }
    }
    public static void recursion(int n, int len) {
        if(n == 0) {
            rst.append("-");
            return ;
        }
        recursion(n-1, len/3);
        for(int i = 0; i < len; i++) {
            rst.append(" ");
        }
        recursion(n-1, len/3);
    }
}