[프로그래머스] 자물쇠와 열쇠, Python3

문제는 여기!

이 문제를 맨 처음에 봤을 때는, 열쇠를 자물쇠에 꽂을 때 자물쇠 영역에 벗어난 부분은 어떻게 처리해야 하는지에 대해 고민이었는데, 짱동빈 형님은 기존의 자물쇠에 가로, 세로를 각각 key 사이즈 * 2 만큼 자물쇠 사이즈를 늘려서 하나씩 꽂는 방법으로 풀이하셨다. 생각외로 아이디어가 간단했는데? 나도 문제 풀때는 기가막힌 아이디어 보다는 아기자기한 꼼수를 쓰는 것도 괜찮겠다 싶었던 문제였다.

주의사항 및 제한사항

key와 lock은 정사각형이며, 각각의 크기는 3 이상 20 이하이다.

key의 사이즈는 항상 자물쇠의 사이즈보다 같거나 작습니다.

풀이전략

우선, 시간 복잡도를 예상했을 때, 열쇠 크기 * 2 + 자물쇠 크기를 해주면 (20 * 2 + 20) ** 2 = 3,600 열쇠는 회전을 할 수 있기 때문에 3,600 * 4 = 14,400 이므로 경우의 수가 그리 크지 않아 완전탐색으로 접근했다.

자물쇠 주변을 key의 크기만큼 덧대어 new_lock을 만들었다. 그림을 보자.

만약 Key의 사이즈가 3, Lock의 사이즈가 5라고 가정했을 때, 기존의 Lock 사이즈 + (Key의 사이즈 * 2)만큼 가로, 세로를 늘린 다음에 가운데에 Lock의 원소를 집어 넣었다.

그다음 새로 만든 Lock의 배열의 0 부터 Key 사이즈 + 기존의 Lock사이즈 까지 이중 반복문을 통해 검사했다. 이때 열쇠도 90도로 돌려야 하기 때문에 이중 반복문 안에 4번 리스트를 더 돌아야 한다.

키를 자물쇠에 꽂을때는 해당 검사 영역만큼 key의 원소를 더하면 된다. 그 후 새로 만든 Lock 배열에서 가운데 있는 Lock의 범위의 원소들이 모두 1인지 체크한다. 모두 1이라면 바로 True를 반환하며, 그렇지 않은 경우는 다시 키를 자물쇠에 빼는 작업을 해야한다. (키를 자물쇠에 꽂는 로직을 반대로 실행하면 된다.) 그 다음, 열쇠를 90도로 돌려주어야 하는데, 이때 나는 zip 함수를 이용해서 간단하게 해결했다.

def get_new_lock(len_key, len_lock, lock):
    new_lock = [[0 for _ in range(2 * len_key + len_lock)] for _ in range(2 * len_key + len_lock)]
    for i in range(len_lock):
        for j in range(len_lock):
            new_lock[i + len_key][j + len_key] = lock[i][j]
    return new_lock


def insert_key(key, lock, y, x):
    for i in range(len(key)):
        for j in range(len(key)):
            lock[y + i][x + j] += key[i][j]


def delete_key(key, lock, y, x):
    for i in range(len(key)):
        for j in range(len(key)):
            lock[y + i][x + j] -= key[i][j]


def is_open(new_lock, len_key, len_lock):
    for i in range(len_key, len_key + len_lock):
        for j in range(len_key, len_key + len_lock):
            if new_lock[i][j] != 1:
                return False
    return True


def rotate_key(key):
    return list(zip(*key[::-1]))


def solution(key, lock):
    len_key = len(key)
    len_lock = len(lock)
    new_lock = get_new_lock(len_key, len_lock, lock)
    for i in range(len_lock + len_key):
        for j in range(len_lock + len_key):
            for k in range(4):
                insert_key(key, new_lock, i, j)
                if is_open(new_lock, len_key, len_lock):
                    return True
                delete_key(key, new_lock, i, j)
                key = rotate_key(key)
    return False