[알고리즘 문제/2020 KAKAO BLIND RECRUITMENT] 자물쇠와 열쇠

정답코드

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

enum class Direction {
    `0`{
        override fun x(x: Int, y: Int, size : Int) = x
        override fun y(x: Int, y: Int, size : Int) = y
    }, `90`{
        override fun x(x: Int, y: Int, size : Int) = (size - 1) - y
        override fun y(x: Int, y: Int, size : Int) = x
    }, `180`{
        override fun x(x: Int, y: Int, size : Int) = (size - 1) - x
        override fun y(x: Int, y: Int, size : Int) = (size - 1) - y
    }, `270`{
        override fun x(x: Int, y: Int, size : Int) = y
        override fun y(x: Int, y: Int, size : Int) = (size - 1) - x
    };

    abstract fun x(x: Int, y: Int, size : Int) : Int
    abstract fun y(x: Int, y: Int, size : Int) : Int
}

class Solution {

    fun solution(key: Array<IntArray>, lock: Array<IntArray>): Boolean {
        enumValues<Direction>().forEach { 
            var rotated = rotate(key, it)
            for(moveX in -(key.size - 1) .. (lock.size-1) + (key.size-1)) {
                for(moveY in -(key.size - 1) .. (lock.size-1) + (key.size-1)) {
                    var movedKey = moveKey(rotated, lock.size, moveX, moveY)
                    var match = plus(movedKey, lock)
                    if(checkOpen(match)) return true
                }
            }
        }
        return false
    }


    fun checkOpen(matrix: Array<IntArray>) : Boolean {
        return matrix.any{ a -> a.any{ it != 1 } }.not()
    }

    fun createMatrix(size : Int) : Array<IntArray> {
        return Array(size, { IntArray(size, {0}) })
    }

    fun moveKey(key: Array<IntArray>, lockSize : Int, moveX : Int, moveY : Int) : Array<IntArray> {
        var moveKey = createMatrix(lockSize)
        for(x in 0 .. lockSize - 1){
            for(y in 0 .. lockSize - 1){

                var movedX = x + moveX
                var movedY = y + moveY

                var validation = x >= 0 && x < key.size && y >= 0 && y < key.size
                var ableToMove = movedX >= 0 && movedX < lockSize && movedY >= 0 && movedY < lockSize
                if(validation && ableToMove) {
                    moveKey[movedX][movedY] = key[x][y]
                }
            } 
        }
        return moveKey
    }

    fun rotate(matrix: Array<IntArray>, direction: Direction) : Array<IntArray> {    
        return createMatrix(matrix.size).mapIndexed {i, e1 -> 
            e1.mapIndexed { j, _ -> 
                var newX = direction.x(i, j, matrix.size)
                var newY = direction.y(i, j, matrix.size)
                matrix[newX][newY]
            }.toIntArray()
        }.toTypedArray()
    }

    fun plus(matrixA: Array<IntArray>, matrixB: Array<IntArray>) : Array<IntArray> {
        return matrixA.mapIndexed { i, e1 -> e1.mapIndexed { j, e2 -> e2 + matrixB[i][j] }.toIntArray() }.toTypedArray()
    }
}


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

    
    /*
     * 000       matrix[0][0]  matrix[0][1]  matrix[0][2]
     * 100       matrix[1][0]  matrix[1][1]  matrix[1][2]
     * 011       matrix[2][0]  matrix[2][1]  matrix[2][2]
    */
    fun draw(matrix: Array<IntArray>) {
        matrix.forEach{       
            it.forEach{           
                a ->print(a)
            }
            println("")
        }
        println("---")
    }
    
    fun testSolution() {
        val key = arrayOf(intArrayOf(0,0,0),intArrayOf(1,0,0),intArrayOf(0,1,1))
        val lock = arrayOf(intArrayOf(1,1,1),intArrayOf(1,1,0),intArrayOf(1,0,1))
        val answer = true

        testTool.test(answer) {
            solution.solution(key, lock)
        }
    }

}

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

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

class EfficiencyTest : TestStrategy {
    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()
}

 

풀이방식

조금 무식한 방법일지 모르지만 열쇠와 자물쇠의 최대 크기가 20이라서 가능한 모든 경우의 수를 확인하는 방법으로 접근했다.

키의 회전과 움직임에 따른 변형된 키값을 가지고 올 수 있도록 (roatate, moveKey) 함수를 각각 구현했다.

moveKey는 움직인 결과로 자물쇠크기의 0배열에서 변형된 키의 돌기 부분만 1이 되도록 배열을 반환했고,

답 도출은 자물쇠와 변형된 키의 각 원소값을 더해 모든 원소가 1이 나오는 경우를 open으로 규정했다.