백준 - 2447 별 찍기 - 10

문제

2447 별 찍기 - 10

note

• 분할 정복, 재귀를 사용하는 문제이지만, 분할 정복, 재귀를 사용하지 않고도 풀린다.

답

1. kotlin code: 분할 정복, 재귀를 사용하지 않는 코드

import kotlin.math.pow

fun main() {
    val input = readln().toInt()
    val stars = getStars(input)
    val output = getOutputString(stars)
    println(output)
}

private fun getStars(input: Int): Array<CharArray> {
    val stars = Array(input) { CharArray(input) { '*' } }
    val log3 = log(input, 3)
    for (l in (0 until log3)) {
        val blockSize = 3.0.pow(l).toInt()
        val to = input - blockSize
        for (y in (blockSize until to)) {
            val blankRow = (y / blockSize % 3) == 1
            for (x in (blockSize until to)) {
                val blankColumn = (x / blockSize % 3) == 1
                if (blankRow && blankColumn) stars[x][y] = ' '
            }
        }
    }
    return stars
}

private fun log(x: Int, base: Int):Int = (kotlin.math.log10(x.toDouble()) / kotlin.math.log10(3.0)).toInt()

private fun getOutputString(stars: Array<CharArray>): StringBuilder {
    val output = StringBuilder()
    for (row in stars) {
        for (column in row) output.append(column)
        output.append('\n')
    }
    return output
}

• Q. 왜 log(input.toDouble(), 3.0)이 아닌, log10(input.toDouble()) / log10(3.0)을 사용할까?
• A. kotlin.math.log(243.0, 3.0)이 5가 아닌 4.9999…가 결과로 나오기 때문이다.

2. kotlin code: 반환 값이 있는 재귀를 사용하는 코드

fun main() {
    val input = readln().toInt()
    val stars = getStars(input)
    val output = getOutputString(stars)
    println(output)
}

private fun getStars(n: Int): Array<CharArray> = when(n) {
    1 -> Array(1) { CharArray(1) {'*'} }
    else -> {
        val output = Array(n) { CharArray(n) {' '} }
        val block = n / 3
        for(y in (0..2)) {
            for(x in (0..2)) {
                if(y == 1 && x == 1) continue
                output.setStar(x*block, y*block, getStars(block))
            }
        }
        output
    }
}

private fun Array<CharArray>.setStar(x: Int, y: Int, starPattern: Array<CharArray>) {
    for ((py, row) in starPattern.withIndex()) {
        for ((px, column) in row.withIndex()) {
            this[py + y][px + x] = column
        }
    }
}

private fun getOutputString(stars: Array<CharArray>): StringBuilder {
    val output = StringBuilder()
    for (row in stars) {
        for (column in row) output.append(column)
        output.append('\n')
    }
    return output
}

3. kotlin code: 반환 값이 있는 재귀 + 캐시를 사용하는 코드

fun main() {
    val input = readln().toInt()
    val cache = hashMapOf(1 to Array(1) { CharArray(1) {'*'} })
    val stars = getStars(input, cache)
    val output = getOutputString(stars)
    println(output)
}

private fun getStars(n: Int, cache: MutableMap<Int, Array<CharArray>>): Array<CharArray> = when {
    cache.containsKey(n) -> cache[n]!!
    else -> {
        val output = Array(n) { CharArray(n) { ' ' } }
        val block = n / 3
        for (y in (0..2)) {
            for (x in (0..2)) {
                if (y == 1 && x == 1) continue
                val stars = getStars(block, cache)
                cache[block] = stars
                output.setStar(x * block, y * block, cache[block]!!)
            }
        }
        output
    }
}

private fun Array<CharArray>.setStar(x: Int, y: Int, starPattern: Array<CharArray>) {
    for ((py, row) in starPattern.withIndex()) {
        for ((px, column) in row.withIndex()) {
            this[py + y][px + x] = column
        }
    }
}

private fun getOutputString(stars: Array<CharArray>): StringBuilder {
    val output = StringBuilder()
    for (row in stars) {
        for (column in row) output.append(column)
        output.append('\n')
    }
    return output
}

4. kotlin code: 반환 값이 없는 재귀를 사용하는 코드(추천)

fun main() {
    val input = readln().toInt()
    val output = Array(input) { CharArray(input) {' '} }
    drawStars(0, 0, input, output)
    val outputString = getOutputString(output)
    println(outputString)
}

private fun drawStars(x:Int, y:Int, n: Int, output: Array<CharArray>): Unit = when(n) {
    1 -> output[x][y] = '*'
    else -> {
        val block = n / 3
        for(y2 in (0..2)) {
            for(x2 in (0..2)) {
                if(x2 == 1 && y2 == 1) continue
                drawStars(x + x2*block, y + y2*block, block, output)
            }
        }
    }
}

private fun getOutputString(stars: Array<CharArray>): StringBuilder {
    val output = StringBuilder()
    for (row in stars) {
        for (column in row) output.append(column)
        output.append('\n')
    }
    return output
}