Programmers. 자물쇠와 열쇠

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 자물쇠와 열쇠

문제 풀이

2차원 배열의 회전을 다뤄보지 않았다면 해결하기 어려울 수 있는 문제였다. 필자도 해결하지 못해 결국 라이트업을 찾고 해결하였다.

문제 조건에서 key를 90도씩 회전하면서 맞추되 1칸부터 key 전체를 맞출 수 있으니 격자배열을 순회하면서 4번 회전해 맞추고 조건이 성립하면 True를 반환하면 되겠다.

• 2차원 배열을 90도 회전시키는 함수 정의
• 주어진 key와 자물쇠를 검사하는 함수 정의
• key가 이동할 수 있는 거리만큼 순회하되 각 지점에서 90도씩 4번 회전하여 검사
• 중간에 true가 나오면 True리턴, 끝까지 순회가 가능하면 False

python 코드

def solution(key, lock):
    def rotate(m):
        N = len(m)
        res = [[0 for _ in range(N)] for _ in range(N)]
        for r in range(N):
            for c in range(N):
                res[c][N - 1 - r] = m[r][c]
        return res
    def check(s_r, s_c, K, L):
        k, l = len(K), len(L)
        v = 2 * (k - 1) + l
        grid = [[0 for _ in range(v)] for _ in range(v)]
        for i in range(k):
            for j in range(k):
                grid[s_r + i][s_c + j] += K[i][j]
        for i in range(l):
            for j in range(l):
                grid[k - 1 + i][k - 1 + j] += L[i][j]
                if grid[k - 1 + i][k - 1 + j] != 1:
                    return False
        return True
    for r in range(len(key) + len(lock) - 1):
        for c in range(len(key) + len(lock) - 1):
            x = key
            for i in range(4):
                x = rotate(x)
                if check(r, c, x, lock) is True:
                    return True
    return False