[Seop's의 코드풀이] 프로그래머스 자물쇠와 열쇠

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

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

 

문제요약

이번에 풀어본 문제는 2020 카카오 블래인드 채용 코딩테스트에서 출제되었던 문제입니다.  

이차원 배열인 Key 와 Lcok이 주어집니다. 각 배열은 0 과 1로 구성되어 있습니다.  

Key를 회전시키거나 이동하여 Lock에 맞다면 True를 Reutrn 하고 맞지 않는다면 False를 리턴합니다.  

Key는 Lock을 벗어나도 됩니다.

 

문제풀이 IDEA

본 문제를 풀때 눈여겨 봐야할 것이 N,M의 크기입니다. 둘다 20 이하입니다. 즉 모든 경우를 다 해볼만하다입니다.  

그렇다면 어떻게 모든 경우를 다 해볼까요? 다음과 같은 Key 와 Lock이 있다고 생각해보겠습니다.

이런식으로 한칸씩 이동하면서 비교해볼 수 있을 것입니다.

또한 key를 회전시켜서 모든 경우를 찾다가 lock이 겹치지 않고 모두 1이라면 True입니다. 

위와 같이 하나씩 이동하면서 비교하는 과정을 컴퓨터에서 작동시키려면 Lock 주변에 빈공간이 있어야 합니다.

Lock 길이의 3배네 해당하는 0배열을 만들고 한가운데 Lock을 넣어주면 됩니다.  

 

본 문제는 효율성보다는 2차원 배열을 얼마나 자유롭게 다룰 수 있는데 초점이 맞추어진것 같습니다. 2차원 배열을 잘 활용할 수 있다면 해결 할 수 있을 것이라 생각됩니다.  다음은 문제를 풀이하는데 있어 큰 설계 틀입니다.  

 

• Lock 배열 *3 크기의 2차원 배열을 만들고 가운데 Lock을 집어넣는다. 
• 시작점을 (N-M)에서부터 2N 까지 Key배열을 그려 자물쇠가 풀리는지 확인한다(Lock 배열이 모두 1이 되고 겹치지 않는지) 
• 자물쇠가 풀리지 않는다면 총 4회전을 거쳐 풀리는지 확인한다. 
• 풀리면 True, 풀리지 않는다면 False를 리턴한다. 

 

Code

질문과 피드백은 언제나 감사드립니다.  

 

import copy
def rotate90(array) :
    lentgh = len(array)
    result = []
    for _ in range(lentgh) :
        result.append([])
    for i in range(lentgh-1, -1, -1) :
        j = 0
        for c in array[i] :
            result[j].append(c)
            j += 1
    return result

def makeCompArray(lock) :
    N = len(lock)
    T = N*3
    result = [[0 for _ in range(T)] for _ in range(T)]
    for i in range(N,N+N) :
        for j in range(N,N+N) :
            result[i][j] = lock[i-(N)][j-(N)]
    return result

def unlock(key, comp, x, y) :
    result = copy.deepcopy(comp)
    for i in range(x, x + len(key)) :
        for j in range(y, y + len(key)) :
            result[i][j] += key[i-x][j-y]
    return result

def checkIsUnlock(array, N) :
    for i in range(N,N+N) :
        for j in range(N,N+N) :
            if array[i][j] != 1 :
                return False
    return True
            

def solution(key, lock):
    answer = True
    compArray = makeCompArray(lock)
    for _ in range(4) :
        for i in range(len(lock) -len(key) + 1, len(lock)*2 + 1): 
            for j in range(len(lock) -len(key) + 1, len(lock)*2 + 1):
                temp = unlock(key, compArray, i, j)
                answer = checkIsUnlock(temp, len(lock))
                if answer :
                    return answer
        key = rotate90(key)
    return answer