[알고리즘 문제/2020 KAKAO BLIND RECRUITMENT] 기둥과 보 설치

보가 뭔지 모르겠어서 찾아본 그림

 

 

현재코드

참고

sooooooyn.tistory.com/32

[2020카카오공채] 기둥과 보 설치

class Solution {

    var SIZE = -1
    var pillers = mutableListOf(mutableListOf<Boolean>())
    var beams = mutableListOf(mutableListOf<Boolean>())

    enum class BuildOrder() {
        PILLER_CONSTRUCT,
        PILLER_DESTRUCT,
        BEAM_CONSTRUCT,
        BEAM_DESTRUCT,
        NONE
    }

    fun solution(size: Int, build_frame: Array<IntArray>): Array<IntArray> {

        var answer = mutableListOf<IntArray>()

        SIZE = size
        pillers = MutableList(SIZE + 1) { MutableList(SIZE + 1) {false} }
        beams = MutableList(SIZE + 1) { MutableList(SIZE + 1) {false} }

        build_frame.forEach{
            process(it)
        }

        for (i in 0..SIZE) {
            for (j in 0..SIZE) {
                if (pillers[i][j]) {
                    answer.add(intArrayOf(i, j, 0))
                }
                if (beams[i][j]) {
                    answer.add(intArrayOf(i, j, 1))
                }
            }
        }

        return answer.toTypedArray()
    }

    fun checkAbleToConstructPiller(x : Int, y : Int) : Boolean {
        if(y == 0) return true
        if(y > 0 && pillers[x][y-1]) return true
        if(x > 0 && beams[x - 1][y]) return true
        if(beams[x][y]) return true
        return false
    }

    fun checkAbleToConstructBeam(x : Int, y : Int) : Boolean {
        if(y > 0 && pillers[x][y-1]) return true
        if(x < SIZE + 1 && y > 0 && pillers[x + 1][y - 1]) return true
        if(x > 0 && x < SIZE + 1 && beams[x - 1][y] && beams[x + 1][y]) return true
        return false
    }

    fun process(frame : IntArray) {
        val posX = frame[0]
        val posY = frame[1]
        when(getBuildOrder(frame[2] == 1, frame[3] == 1)) {
            BuildOrder.PILLER_CONSTRUCT -> {
                if(checkAbleToConstructPiller(posX, posY)){
                    pillers[posX][posY] = true
                }
            }
            BuildOrder.BEAM_CONSTRUCT -> {
                if(checkAbleToConstructBeam(posX,posY)){
                    beams[posX][posY] = true
                }
            }
            BuildOrder.PILLER_DESTRUCT ->{
                var ableToDestruct = true
                pillers[posX][posY] = false

                if(posY < SIZE + 1 && pillers[posX][posY + 1] && !checkAbleToConstructPiller(posX, posY + 1)) ableToDestruct = false
                else if(posX > 0 && posY < SIZE + 1 && beams[posX - 1][posY + 1] && !checkAbleToConstructBeam(posX - 1, posY + 1)) ableToDestruct = false
                else if(posX < SIZE + 1 && posY < SIZE + 1 && beams[posX][posY + 1] && !checkAbleToConstructBeam(posX, posY + 1)) ableToDestruct = false

                if(!ableToDestruct) {
                    pillers[posX][posY] = true
                }
            }
            BuildOrder.BEAM_DESTRUCT -> {
                var ableToDestruct = true
                beams[posX][posY] = false

                if(pillers[posX][posY] && !checkAbleToConstructPiller(posX, posY)) ableToDestruct = false
                else if(posX < SIZE + 1 && pillers[posX + 1][posY] && !checkAbleToConstructPiller(posX + 1, posY)) ableToDestruct = false
                else if(posX > 0 && beams[posX - 1][posY] && !checkAbleToConstructBeam(posX - 1, posY)) ableToDestruct = false
                else if(posX < SIZE + 1 && beams[posX + 1][posY] && !checkAbleToConstructBeam(posX + 1, posY)) ableToDestruct = false

                if(!ableToDestruct) {
                    beams[posX][posY] = true
                }
            }
            else->{}
        }
    }


    private fun getBuildOrder(isBeam: Boolean, isConstruct: Boolean) : BuildOrder {
        return when {
            !isBeam && isConstruct -> BuildOrder.PILLER_CONSTRUCT
            isBeam && isConstruct -> BuildOrder.BEAM_CONSTRUCT
            !isBeam && !isConstruct -> BuildOrder.PILLER_DESTRUCT
            isBeam && !isConstruct -> BuildOrder.BEAM_DESTRUCT
            else -> BuildOrder.NONE
        }
    }


}

 

 

 

 

괜히 코드가 복잡해짐... 하나 정보를 체크하기 위해서 sub을 확인하는 것은 효율적이지 않다.

삭제 시 기둥은 왼쪽보 상단기둥 오른쪽보를 확인해야하고

보는 왼쪽보 왼쪽기둥 오른쪽기둥 오른쪽보를 확인해야한다.

결과를 머리속으로 그릴때 보와 기둥의 상대 위치가 다르기때문에 헷갈리수 있음 주의!

import kotlin.test.*
import kotlin.time.*

class Solution {

    var board : Array<Array<Cell>>? = null

    data class Cell(val x : Int, val y: Int) {
        var isPillerConstructed = false
        var isBeamConstructed = false
        var isSubPillerConstructed = false
        var isSubBeamConstructed = false

        fun checkAbleToConstructPiller(board : Array<Array<Cell>>) : Boolean {
            val isUpperFloor = y == 0
            val isUpperPiller = isSubPillerConstructed
            val isUperBeam = isBeamConstructed || isSubBeamConstructed
            return isUpperFloor || isUpperPiller || isUperBeam
        }

        fun checkAbleToConstructBeam(board : Array<Array<Cell>>) : Boolean {
            val isUpperPiller = isSubPillerConstructed || ((x + 1 < board.size) && board[x+1][y].isSubPillerConstructed)
            val isBothSideBeam = isSubBeamConstructed && (x + 1 < board.size) && board[x+1][y].isBeamConstructed
            return isUpperPiller || isBothSideBeam
        }


        fun checkAbleToDestruct(board : Array<Array<Cell>>) : Boolean {
            var answer = true

            for(i in x - 1 .. x + 1){
                for (j in y -1 .. y + 1){
                    if(i >= 0 && i < board.size && j >= 0 && j < board.size){
                        if(board[i][j].isPillerConstructed) {
                            board[i][j].isPillerConstructed = false
                            board[i][j + 1].isSubPillerConstructed = false
                            if(!board[i][j].checkAbleToConstructPiller(board)) answer = false
                            board[i][j].isPillerConstructed = true
                            board[i][j + 1].isSubPillerConstructed = true
                        } 
                        if(board[i][j].isBeamConstructed) {
                            board[i][j].isBeamConstructed = false
                            board[i+1][j].isSubBeamConstructed = false
                            if(!board[i][j].checkAbleToConstructBeam(board)) answer = false
                            board[i][j].isBeamConstructed = true
                            board[i+1][j].isSubBeamConstructed = true
                        }
                    }
                }
            }
            return answer
        }
    }

    class BuildOrder(build_order : IntArray) {
        val posX : Int
        val posY : Int
        val isBeam : Boolean
        val isConstruct : Boolean

        init {
            posX = build_order[0]
            posY = build_order[1]
            isBeam = build_order[2] == 1
            isConstruct = build_order[3] == 1
        }

        override fun toString() : String {
            var obj = if(isBeam) " 보 " else "기둥"
            var install = if(isConstruct) "설치" else "제거"
            return "[$posX,$posY] $obj $install"
        }
    }

    fun solution(size: Int, build_frame: Array<IntArray>): Array<IntArray> {
        var answer = arrayOf<IntArray>()
        var orders = mutableListOf<BuildOrder>()

        board = makeBoard(size + 1)
        board?.also { _board ->
            build_frame.forEach{
                var order = BuildOrder(it)
                board = doOrder(_board, order)
            }
            answer = convertToAnswer(_board)
        }

        return answer
    }

    fun convertToAnswer(board: Array<Array<Cell>>) : Array<IntArray> {
        var answer = mutableListOf<IntArray>()
        board.forEachIndexed {i, ei ->
            ei.forEachIndexed {j, ej ->
                val value = when {
                    board[i][j].isPillerConstructed -> 0
                    board[i][j].isBeamConstructed -> 1
                    else -> -1
                }
                if(value > -1) answer.add(intArrayOf(i, j, value))
            }
        }
        answer.sortWith(Comparator{ a, b ->
            ((a[0] * 1000000) + (a[1] * 1000) + (a[2])) - ((b[0] * 1000000) + (b[1] * 1000) + (b[2]))
        })

        return answer.toTypedArray()
    }

    fun makeBoard(size : Int) : Array<Array<Cell>> {
        return Array(size, { i -> Array(size, { j -> Cell(i, j)}) })
    }

    fun drawBoard(board: Array<Array<Cell>>) {
        var rotatedBoard = rotate(board)
        rotatedBoard.forEach { i ->
            i.forEach { j ->
                var a = when {
                    j.isPillerConstructed->"■"
                    j.isSubPillerConstructed->"□"
                    else -> "x"
                }
                var b = when {
                    j.isBeamConstructed->"●"
                    j.isSubBeamConstructed->"○"
                    else -> "x"
                }
                print("[$a$b]")
            }
            println("")
        }
    }



    fun rotate(board: Array<Array<Cell>>) : Array<Array<Cell>> {    
        return makeBoard(board.size).mapIndexed {i, e1 -> 
            e1.mapIndexed { j, _ -> 
                var newX = j
                var newY = (board.size - 1) - i
                board[newX][newY]
            }.toTypedArray()
        }.toTypedArray()
    }

    fun doOrder(board: Array<Array<Cell>>, order :BuildOrder) : Array<Array<Cell>> {

        when {
            order.isBeam && order.isConstruct -> {
                if(board[order.posX][order.posY].checkAbleToConstructBeam(board)){
                    board[order.posX][order.posY].isBeamConstructed = true
                    board[order.posX + 1][order.posY].isSubBeamConstructed = true
                }
            }
            !order.isBeam && order.isConstruct -> {
                if(board[order.posX][order.posY].checkAbleToConstructPiller(board)){
                    board[order.posX][order.posY].isPillerConstructed = true
                    board[order.posX][order.posY + 1].isSubPillerConstructed = true
                }
            } 
            order.isBeam && !order.isConstruct -> {
                board[order.posX][order.posY].isBeamConstructed = false
                board[order.posX + 1][order.posY].isSubBeamConstructed = false
                if(!board[order.posX][order.posY].checkAbleToDestruct(board)) {
                    board[order.posX][order.posY].isBeamConstructed = true
                    board[order.posX + 1][order.posY].isSubBeamConstructed = true 
                }
            } 
            !order.isBeam && !order.isConstruct ->{ 
                board[order.posX][order.posY].isPillerConstructed = false
                board[order.posX][order.posY + 1].isSubPillerConstructed = false
                if(!board[order.posX][order.posY].checkAbleToDestruct(board)) {
                    board[order.posX][order.posY].isPillerConstructed = true
                    board[order.posX][order.posY + 1].isSubPillerConstructed = true 
                }
            }
            else -> {}
        }

        return board
    }

}


class SolutionTest(val solution : Solution, val testTool : TestStrategy = NormalTest()) {

    fun testSolution() {

        val testCase1 = Triple(5, "[[1,0,0,1],[1,1,1,1],[2,1,0,1],[2,2,1,1],[5,0,0,1],[5,1,0,1],[4,2,1,1],[3,2,1,1]]", "[[1,0,0],[1,1,1],[2,1,0],[2,2,1],[3,2,1],[4,2,1],[5,0,0],[5,1,0]]")
        val testCase2 = Triple(5, "[[0,0,0,1],[2,0,0,1],[4,0,0,1],[0,1,1,1],[1,1,1,1],[2,1,1,1],[3,1,1,1],[2,0,0,0],[1,1,1,0],[2,2,0,1]]", "[[0,0,0],[0,1,1],[1,1,1],[2,1,1],[3,1,1],[4,0,0]]")

        val testCases = listOf(testCase1 , testCase2)

        testCases.forEach { case ->
            var (size, raw_build_frame, raw_answer) = case
            testTool.testArray(parseArrayIntArray(raw_answer)) {
                solution.solution(size, parseArrayIntArray(raw_build_frame))
            }
        }
    }

    companion object {
        fun parseArrayIntArray(s : String) : Array<IntArray> {
            val A = s.subSequence(2, s.length -2).split("],[")
            return A.map{ a->
                val B = a.split(",")
                B.map{ b-> b.toInt() }.toIntArray()
            }.toTypedArray()
        }
    }
}

interface TestStrategy {
    fun testArray(answer : Array<*>, testBlock: ()-> Array<*>)
    fun<T> test(answer : T, testBlock: () -> T)
}

class NormalTest : TestStrategy {

    override fun testArray(answer : Array<*>, testBlock: ()-> Array<*>) {
        val result = testBlock()
        println("------------")
        assertTrue(result.contentDeepEquals(answer), "epected : $answer, actural : $result")
    }

    override fun<T> test(answer : T, testBlock: ()->T) {
        val result = testBlock()
        println("------------")
        assertEquals(answer, result, "epected : $answer, actural : $result")
    }
}

class EfficiencyTest : TestStrategy {

    override fun testArray(answer : Array<*>, testBlock: ()-> Array<*>) {
        val (result, duration) = measureTimedValue { testBlock() }
        println("------------")
        println("duration : $duration")
        assertTrue(result.contentDeepEquals(answer), "epected : $answer, actural : $result")
    }

    override fun<T> test(answer : T, testBlock: ()->T) {
        val (result, duration) = measureTimedValue { testBlock() }
        println("------------")
        println("duration : $duration")
        assertEquals(answer, result, "epected : $answer, actural : $result")
    }
}

fun main() {
    val solution = Solution()
    val solutionTest = SolutionTest(solution)

    solutionTest.testSolution()
}

 

 

이슈

예제는 통과하는데 정확도 테스트에선 2문제(6번, 7번)만 통과 된다.

의심스러운 부분은 삭제하는 로직...