프로그래머스 자물쇠와 열쇠 Kotlin (구현) 2022-06-21 코드 추가

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/60059

코딩테스트 연습 - 자물쇠와 열쇠

문제 설명

고고학자인 "튜브"는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다.

잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.

자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.

열쇠를 나타내는 2차원 배열 key와 자물쇠를 나타내는 2차원 배열 lock이 매개변수로 주어질 때, 열쇠로 자물쇠를 열수 있으면 true를, 열 수 없으면 false를 return 하도록 solution 함수를 완성해주세요.

제한사항

• key는 M x M(3 ≤ M ≤ 20, M은 자연수)크기 2차원 배열입니다.
• lock은 N x N(3 ≤ N ≤ 20, N은 자연수)크기 2차원 배열입니다.
• M은 항상 N 이하입니다.
• key와 lock의 원소는 0 또는 1로 이루어져 있습니다.
  • 0은 홈 부분, 1은 돌기 부분을 나타냅니다.

---

입출력 예

입출력 예에 대한 설명

key를 시계 방향으로 90도 회전하고, 오른쪽으로 한 칸, 아래로 한 칸 이동하면 lock의 홈 부분을 정확히 모두 채울 수 있습니다.

풀이

lock의 크기가 4 X 4

key의 크기가 3 X 3일 때의 모습이다.

key는 오른쪽으로 한 칸, 아래로 한 칸 이동하는 것뿐만 아니라 시계방향으로 90도 회전도 가능하니,

회전하지 않았을 때, 90도 회전했을 때, 180도 회전했을 때, 270도 회전했을 때 총 4번의 회전한 면에 대해

위의 그림처럼 key를 lock의 왼쪽 위에서부터 오른쪽 아래까지 검사하면 된다.

코드1

class Solution {
    
    fun rotate(key : Array<IntArray>) : Array<IntArray>{
        val keyCopy = Array(key.size){IntArray(key.size)}
        for(i in key.indices){
            for(j in key.indices){
                keyCopy[i][j] = key[key.size-1-j][i]
            }
        }
        return keyCopy
    }
    
    fun check(board : Array<IntArray>, key : Array<IntArray>,lock : Array<IntArray>,r : Int, c : Int):Boolean{
        //깊은 복사 : 원본 배열의 값이 안 바뀜
        val boardCopy = Array(board.size){IntArray(board.size)}
        for(i in board.indices){
            for(j in board[i].indices){
                boardCopy[i][j] = board[i][j]
            }
        }
        
       //board에 key 합치기
        for(i in key.indices){
            for(j in key.indices){
                boardCopy[r+i][c+j] +=key[i][j]
            }
        }

         //a,b가 lock의 범위 내일 때, board[a][b]의 값이 2또는 0이라면 어차피 열 수 없으므로 바로 false return
        //이를 모두 통과한다면 return true
        // println("${key.size-1} ${boardSize}")
        for(i in key.size-1 until board.size-(key.size-1)){
            for(j in key.size-1 until board.size-(key.size-1)){
                if(boardCopy[i][j]!=1){
                    return false
                }
            }
        }
        return true
    }
    
    fun solution(key: Array<IntArray>, lock: Array<IntArray>): Boolean {
        val boardSize = (key.size-1)*2+lock.size
        val board = Array(boardSize){IntArray(boardSize)}
        //자물쇠는 고정이므로 보드의 중앙에 미리 저장
        for(i in key.size-1 until boardSize-(key.size-1)){
            for(j in key.size-1 until boardSize-(key.size-1)){
                board[i][j]=lock[i-(key.size-1)][j-(key.size-1)]        
            }
        }
        //자물쇠의 왼쪽 맨 위에 걸치는 key부터 자물쇠의 오른쪽 맨 아래에 걸치는 key까지 검사
        var keyCopy = key
        
        for(t in 0 until 4){      
            for(i in 0 until boardSize-(key.size-1)){
                for(j in 0 until boardSize-(key.size-1)){
                    if(check(board,keyCopy,lock,i,j)) return true
                }
            }
            //키를 총 4번 회전
            if(t==3)continue
           keyCopy = rotate(keyCopy)
        }
        return false
    }
}

 

코드2

class Solution {
    lateinit var graph: Array<IntArray>

    fun match(sr: Int, sc: Int, key: Array<IntArray>, lock: Array<IntArray>): Boolean {

        var isMatch = true
        for (r in key.indices) {
            for (c in key.indices) {
                val nr = sr+r
                val nc = sc+c
                graph[nr][nc]+=key[r][c]
            }
        }
        label@for(r in lock.indices){
            for(c in lock.indices){
                if(graph[20+r][20+c]!=1){
                    isMatch = false
                    break@label
                }
            }
        }

        if(!isMatch){
            for (r in key.indices) {
                for (c in key.indices) {
                    val nr = sr+r
                    val nc = sc+c
                    graph[nr][nc] -= key[r][c]
                }
            }
        }

        return isMatch
    }

    fun rotate(key: Array<IntArray>){
        val temp = Array(key.size){IntArray(key[0].size)}
        for(r in key.indices){
            for(c in key[0].indices){
                temp[r][c] = key[key.size-c-1][r]
            }
        }
        for(r in key.indices){
            for(c in key[0].indices){
                key[r][c] = temp[r][c]
            }
        }
    }

    fun solution(key: Array<IntArray>, lock: Array<IntArray>): Boolean {
        //preset
        graph = Array(60) { IntArray(60) }
        for (i in lock.indices) {
            for (j in lock.indices) {
                graph[20 + i][20 + j] = lock[i][j]
            }
        }
        //solve
        for (i in 0 until 4) {
            //match
            for(r in 0 until graph.size - key.size){
                for(c in 0 until graph.size - key.size){
                    if(match(r,c,key,lock)) return true
                }
            }
            //rotate
            if(i<3)  rotate(key)
        }
        return false
    }
}