2020 카카오 공채 코딩테스트 - 자물쇠와 열쇠

[풀이과정]

정말 매우 고생한 문제였다.

이상하게 생각이 꼬여 계속 테스트 케이스에서 실패하는 바람에 거의 반나절을 넘게 푼 것 같다.

우선 key를 한칸씩 이동시키며 lock과 만날 수 있는 모든 경우의 수를 고려해주면 된다.

내 경우엔 lock의 왼쪽 하단부터 오른쪽 상단까지 이동시키며 자물쇠의 해제 여부를 판단하였다.

이것을 key를 회전시켜가며 4번 진행해주면 된다.

문제 자체는 딱히 고차원의 알고리즘이나 사고를 필요로 하지 않기 때문에 배열과 인덱스를 다루는 부분 그리고 조건에서 실수만

하지 않는다면 무난히 풀 수 있는 문제라고 본다.

 

 

[사용언어]

Kotlin

 

[소스코드]

 
/**
 * rightTopVertexIndex -> key 의 오른쪽 위 모서리 좌표
 * leftBottomVertexIndex -> key 의 왼쪽 아래 모서리 좌표
 * key 를 [key 의 오른쪽 위 모서리가 lock 의 왼쪽 아래와 일치하는 시점]부터
 * [key 의 왼쪽 아래 모서리가 lock 의 오른쪽 위 모서리와 일치하는 시점]까지 움직이며 겹쳐진 부분을 비교한다
 * **/
fun solution(key: Array<IntArray>, lock: Array<IntArray>): Boolean {
    var answer = false
    var rotatedArray = key.copyOf()
    repeat(4) {
        if (check(rotatedArray, lock)) return true
        rotatedArray = rotateArray(rotatedArray)
    }
    return answer
}
fun check(key: Array<IntArray>, lock: Array<IntArray>): Boolean {
    var answer = false
    val m = key.size
    val n = lock.size
    // key 와 lock 이 한 칸 겹쳐질 때의 최대 사이즈
    val size = ((n-1)+m-1)
    for (rightTopVertexIndexX in 0..size ) {
        checkPoint@
        for (rightTopVertexIndexY in 0..size) {
            // lock 의 칸들을 확인한다.
            val checkList = Array(n) { i ->
                BooleanArray(n) { j ->
                    lock[i][j]==1
                }
            }
            // key 의 왼쪽 아래 모서리 좌표
            val leftBottomVertexIndexX = rightTopVertexIndexX-(m-1)
            val leftBottomVertexIndexY = rightTopVertexIndexY-(m-1)
            // key-lock 이 겹쳐진 부분의 key 모서리 좌표
            val overlappedLeftBottomVertexIndexX = if (leftBottomVertexIndexX>0) leftBottomVertexIndexX else 0
            val overlappedLeftBottomVertexIndexY = if (leftBottomVertexIndexY>0) leftBottomVertexIndexY else 0
            val overlappedRightTopVertexIndexX = if (rightTopVertexIndexX>n-1) n-1 else rightTopVertexIndexX
            val overlappedRightTopVertexIndexY = if (rightTopVertexIndexY>n-1) n-1 else rightTopVertexIndexY
            // 현재 key-lock 이 겹치는 부분을 체크한다
            for (i in overlappedLeftBottomVertexIndexY..overlappedRightTopVertexIndexY) {
                for (j in overlappedLeftBottomVertexIndexX..overlappedRightTopVertexIndexX) {
                    // key 기준으로 변환한 겹쳐진 부분의 모서리 인덱스
                    val _i = i-leftBottomVertexIndexY
                    val _j = j-leftBottomVertexIndexX
                    if (key[_i][_j] == lock[i][j]) {
                        continue@checkPoint
                    } else {
                        checkList[i][j] = true
                    }
                }
            }
            // 전체 리스트를 체크한다
            for (i in checkList.indices) {
                for (j in checkList.indices) {
                    if (!checkList[i][j]) continue@checkPoint
                }
            }
            return true
        }
    }
    return answer
}
fun rotateArray(arr: Array<IntArray>): Array<IntArray> {
    return Array(arr.size) { i ->
        IntArray(arr.size) { j ->
            arr.reversedArray()[j][i]
        }
    }
}