자물쇠와 열쇠.md

날짜

2021-06-24 ~ 2021-06-25 2022-04-26

문제 (2020 카카오 신입 공채)

https://programmers.co.kr/learn/courses/30/lessons/60059

문제 유형

두 이차원 배열을 비교하는 구현 중심의 문제

Code

1차

# 열쇠 90도 회전
def rotate_90_degree(key, m):
    rotated_key = [[0] * m for _ in range(m)]
    for i in range(m):
        for j in range(m):
            rotated_key[j][m - 1 - i] = key[i][j]
    
    return rotated_key

# 열쇠와 자물쇠가 일치하는지 확인 -> 모두 1이어야함
def check(lock, n):
    for i in range(n):
        for j in range(n):
            if lock[n + i][n + j] in [0, 2]:
                return False
    return True

def solution(key, lock):
    n, m = len(lock), len(key)
    
    # 검사의 편의를 위해 자물쇠 영역을 3배로 확장한다
    new_lock = [[1] * (3 * n) for _ in range(3 * n)]
    
    # 새로운 자물쇠의 가운데에 원래 자물쇠를 복제한다
    for i in range(n):
        for j in range(n):
            new_lock[n + i][n + j] = lock[i][j]
    
    # 90 ~ 360도 회전
    for _ in range(4):
        key = rotate_90_degree(key, m)
        
        # 완전탐색으로 열쇠를 자물쇠에 모조리 맞춰본다
        for i in range(2 * n):
            for j in range(2 * n):
                
                # 열쇠를 자물쇠와 맞춰보는 과정
                for k in range(m):
                    for l in range(m):
                        new_lock[i + k][j + l] += key[k][l]
                
                # lock에 해당하는 영역의 값이 모두 1인지 확인한다
                if check(new_lock, n) == True:
                    return True
                
                # new_lock을 원래 상태로 복구한다
                for k in range(m):
                    for l in range(m):
                        new_lock[i + k][j + l] -= key[k][l]
            
    return False

2차

def rotate(key, length):
    rotated = [[0] * length for _ in range(length)]
    for i in range(length):
        for j in range(length):
            rotated[j][length-1-i] = key[i][j]
            
    return rotated

def check(lock, length):
    for i in range(length):
        for j in range(length):
            if lock[length+i][length+j] != 1:
                return False
    return True

def solution(key, lock):
    n, m = len(lock), len(key)
    extended_lock = [[1] * (3 * n) for _ in range(3 * n)]
    for i in range(n):
        for j in range(n):
            extended_lock[n+i][n+j] = lock[i][j]
            
    for _ in range(4):
        key = rotate(key, m)
            
        for i in range(2*n):
            for j in range(2*n):
                for x in range(m):
                    for y in range(m):
                        extended_lock[i + x][j + y] += key[x][y]

                if check(extended_lock, n):
                    return True

                for x in range(m):
                    for y in range(m):
                        extended_lock[i+x][j+y] -= key[x][y]
            
    return False

3차 (코틀린)

class Solution {
    var zeroCount = 0
    
    fun solution(key: Array<IntArray>, lock: Array<IntArray>): Boolean {
        // 0,90,180,270도 회전한 열쇠
        val keyList: Array<Array<IntArray>> = Array(4) {
            Array(key.size) {
                IntArray(key.size)
            }
        }

        zeroCount = countZeroInLock(lock) // 자물쇠의 홈 개수
        makeAllKey(keyList, key) // 각 열쇠 생성
        return isUnLockable(keyList, lock)
    }
    
    fun isUnLockable(keyList: Array<Array<IntArray>>, lock: Array<IntArray>): Boolean {
        for (key in keyList) {
            for (row in 0 - key.lastIndex until lock.size) {
                for (col in 0 - key.lastIndex until lock.size) {
                    // 열쇠(m-1, m-1)-자물쇠(0,0) ~ 열쇠(0.0)-자물쇠(n-1, n-1) 를 맞춰보면서 확인
                    if (isMatched(key, lock, row, col)) {
                        return true
                    }
                }
            }
        }
        
        return false
    }
    
    // 다른 조건을 만족시키면서, 열쇠의 돌기와 자물쇠의 홈이 만나는지 확인한다
    fun isMatched(key: Array<IntArray>, lock: Array<IntArray>, startRow: Int, startCol: Int): Boolean {
        var tempZeroCount = zeroCount // 자물쇠 홈 개수
        
        for (i in key.indices) {
            val lockRow = startRow + i
            
            for (j in key.indices) {
                val lockCol = startCol + j
                
                // 열쇠가 자물쇠를 벗어나도 상관x
                if (lockRow !in lock.indices || lockCol !in lock.indices) continue
                // 돌기와 돌기가 만나면 안됨
                if (key[i][j] == 1 && lock[lockRow][lockCol] == 1) {
                    return false
                }
                // 돌기-홈이 만난 경우
                if (key[i][j] == 1 && lock[lockRow][lockCol] == 0) {
                    tempZeroCount--
                }
            }
        }
        
        // 열쇠가 자물쇠의 홈을 모두 채웠는지 확인
        return tempZeroCount == 0 
    }
    
    fun makeAllKey(keyList: Array<Array<IntArray>>, key: Array<IntArray>) {
        keyList[0] = key
        rotate90(keyList[0], keyList[1])
        rotate90(keyList[1], keyList[2])
        rotate90(keyList[2], keyList[3])
    }
    
    fun rotate90(from: Array<IntArray>, to: Array<IntArray>) {
        for (row in from.indices) {
            for (col in from.indices) {
                to[col][from.lastIndex - row] = from[row][col]
            }
        }
    }
    
    fun countZeroInLock(lock: Array<IntArray>): Int {
        var count = 0
        
        for (row in lock.indices) {
            for (col in lock.indices) {
                if (lock[row][col] == 0) {
                    count++
                }
            }
        }
        
        return count
    }
}

풀이

반복문을 통해 (열쇠[m-1][m-1] - 자물쇠[0][0]) ~ (열쇠[0][0] - 자물쇠[n-1][n-1])까지 전부 확인해서, 열쇠의 돌기와 자물쇠 홈의 위치만 정확히 일치하는 경우가 있는지 알아본다. 그리고 이것을 90도 ~ 360도에 대해 모두 처리한다.

열쇠와 자물쇠의 일치하는지 확인 과정에서, 자물쇠의 크기를 3배 크게 만들면 열쇠가 자물쇠 영역을 벗어나는 경우를 더 쉽게 확인할수 있다.

Feedback

• check()에서 if count == n * n 으로 확인하면, 돌기와 돌기가 만나서 2가 되는 경우를 True로 판정할 수 있다.
• 이차원 배열 탐색 문제에서 상황에 따라 배열의 크기를 늘리면 배열의 크기를 벗어나는 경우를 더 편하게 처리할 수 있다.
• 정사각 행렬 90도 회전 <- 규칙을 파악해서 해결