프로그래머스 - 자물쇠와 열쇠 (카카오 2020)

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

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

CNN의 Convolution Layer가 생각나는 문제다. CNN 개념을 알고 있다면 해결 방식을 어렵지 않게 생각해낼 수 있다.

 

def solution(key, lock):
    answer = False
    rotate_count = 0
    n, m = len(key), len(lock)

    for _ in range(n-1):
        for l in lock:
            l.insert(0, 0)
            l.append(0)

    for _ in range(len(key)-1):
        temp = [0] * (m + ((n - 1) * 2))
        lock.insert(0, temp)
        lock.append(temp)

겉에 zero padding을 씌우는 과정이다. insert와 append를 이용해 lock의 각 원소(배열)의 양 끝에 0을 채워넣는데, 이 때 0은 key 길이 - 1개만큼 씌워준다.

 

그리고 2번째 for loop에서 lock 배열 양 끝에 insert와 append로 zero padding을 채워넣는다. zero padding의 길이와 갯수는 key 배열 길이와 lock 배열 길이에 따라 달라진다.

 

 

 

while rotate_count < 4:
        if check_unlock(key, lock):
            answer = True
            break
        else:
            key = rotate90(key)
            rotate_count += 1

rotate_count가 4가 되면 반복문은 자동으로 종료된다. 90도씩 4번을 돌면 360를 돈 것이기 때문에 더 돌 필요가 없다.

우리는 자물쇠를 풀 수 있는지 확인하는 함수, 그리고 key를 90도로 돌릴 함수 2개를 구현해야 한다.

 

 

 

def rotate90(array):
    n = len(array)
    arr = [[0] * n for _ in range(n)]
    i2, j2 = 0, 0
    for i in range(n):
        for j in range(n-1, -1, -1):
            arr[i2][j2] = array[j][i]
            j2 += 1
        j2 = 0
        i2 += 1
    return arr

 

90도로 회전된 2차원 배열을 return하는 함수이다.

 

 

 

def check_unlock(key, lock):
    n, m = len(key), len(lock)
    start = n-1
    end = m - (n-1)

    for i in range(0, end):
        for j in range(0, end):
            copy_lock = copy.deepcopy(lock)

            for k in range(0, n):
                for l in range(0, n):
                    copy_lock[i+k][j+l] += key[k][l]

            flag = True
            for k in range(start, end):
                for l in range(start, end):
                    if copy_lock[k][l] != 1:
                        flag = False
                        break
            if flag:
                return True
    return False

copy_lock의 padding을 포함해서 key가 칠해질 수 있는 가장 마지막까지 모든 경우를 따져 key값을 더한다.

padding이 포함되지 않은 실제 lock 범위가 전부 1이라면 (0이나 2일 경우에는 탈락) 자물쇠를 열 수 있으므로 true를 return한다.

 

전체 코드

import copy

def rotate90(array):
    n = len(array)
    arr = [[0] * n for _ in range(n)]
    i2, j2 = 0, 0
    for i in range(n):
        for j in range(n-1, -1, -1):
            arr[i2][j2] = array[j][i]
            j2 += 1
        j2 = 0
        i2 += 1
    return arr

def check_unlock(key, lock):
    n, m = len(key), len(lock)
    start = n-1
    end = m - (n-1)

    for i in range(0, end):
        for j in range(0, end):
            copy_lock = copy.deepcopy(lock)

            for k in range(0, n):
                for l in range(0, n):
                    copy_lock[i+k][j+l] += key[k][l]

            flag = True
            for k in range(start, end):
                for l in range(start, end):
                    if copy_lock[k][l] != 1:
                        flag = False
                        break
            if flag:
                return True
    return False


def solution(key, lock):
    answer = False
    rotate_count = 0
    n, m = len(key), len(lock)

    for _ in range(n-1):
        for l in lock:
            l.insert(0, 0)
            l.append(0)

    for _ in range(len(key)-1):
        temp = [0] * (m + ((n - 1) * 2))
        lock.insert(0, temp)
        lock.append(temp)

    while rotate_count < 4:
        if check_unlock(key, lock):
            answer = True
            break
        else:
            key = rotate90(key)
            rotate_count += 1

    return answer