프로그래머스 : 자물쇠와 열쇠

정말 오랜만에 문제를 해결한 것 같아 뿌듯하네요!

풀이는 다음과 같습니다.
(자물쇠의 한 변의 크기는 M, 열쇠의 한 변의 크기는 N이라고 하겠습니다.)

1. 자물쇠를 이동시킬 수 있는 영역을 마련하기 위해 M + 2 * (N - 1) 크기의 배열을 생성합니다.

def createExtendedMatrix(key, lock):
    M, N = len(key), len(lock)
    extended = [[0] * (M + 2 * (N - 1)) for _ in range(M + 2 * (N - 1))]
    for row in range(M - 1, M + N - 1):
        for col in range(M - 1, M + N - 1):
            extended[row][col] = lock[row - M + 1][col - M + 1]
    return extended

• + 해당 크기는 따로 공식이 있는 건 아니고, 그려가며 구했습니다!
• + 큰 배열을 만든 후에는 가운데에 자물쇠를 위치시킵니다.

2. 해당 배열에 자물쇠를 위치시키고, 열쇠의 시작지점을 바꿔가면서 이동합니다.

# 자물쇠의 시작지점을 바꿔가며 큰 배열에 자물쇠를 복사합니다.
# startRow, startCol은 자물쇠의 시작지점을 의미합니다.
 
def search(key, lock):
    M, N = len(key), len(lock)
    searchResult = False
    for startRow in range(M + N - 1):
        for startCol in range(M + N - 1):
            extended = createExtendedMatrix(key, lock)
            for row in range(M):
                for col in range(M):
                    extended[startRow + row][startCol + col] += key[row][col]
            searchResult = checkKeyMatchesLock(M, N, extended)
            if searchResult:
                return True

3. 열쇠를 계속 이동시키면서, 열쇠와 자물쇠가 들어맞는지 (자물쇠 영역의 원소가 모두 1인지)를 체크합니다.

def checkKeyMatchesLock(M, N, extended):
    for row in range(M - 1, M + N - 1):
        for col in range(M - 1, M + N - 1):
            if extended[row][col] != 1:
                return False
    return True

4. 이후 회전시키면서 위 과정을 반복합니다.

def rotate(key):
    M = len(key)
    rotatedKey = [[0] * M for _ in range(M)]
    for row in range(M):
        for col in range(M):
            rotatedKey[row][col] = key[M - col - 1][row]
    return rotatedKey

전체 코드 (Python)

def rotate(key):
    M = len(key)
    rotatedKey = [[0] * M for _ in range(M)]
    for row in range(M):
        for col in range(M):
            rotatedKey[row][col] = key[M - col - 1][row]
    return rotatedKey


def createExtendedMatrix(key, lock):
    M, N = len(key), len(lock)
    extended = [[0] * (M + 2 * (N - 1)) for _ in range(M + 2 * (N - 1))]
    for row in range(M - 1, M + N - 1):
        for col in range(M - 1, M + N - 1):
            extended[row][col] = lock[row - M + 1][col - M + 1]
    return extended


def search(key, lock):
    M, N = len(key), len(lock)
    searchResult = False
    for startRow in range(M + N - 1):
        for startCol in range(M + N - 1):
            extended = createExtendedMatrix(key, lock)
            for row in range(M):
                for col in range(M):
                    extended[startRow + row][startCol + col] += key[row][col]
            searchResult = checkKeyMatchesLock(M, N, extended)
            if searchResult:
                return True


def checkKeyMatchesLock(M, N, extended):
    for row in range(M - 1, M + N - 1):
        for col in range(M - 1, M + N - 1):
            if extended[row][col] != 1:
                return False
    return True


def solution(key, lock):
    for _ in range(4):
        key = rotate(key)
        print(key)
        searchResult = search(key, lock)
        if searchResult:
            return True
    return False


# solution([[0, 0, 0], [1, 0, 0], [0, 1, 1]],
#          [[1, 1, 1], [1, 1, 0], [1, 0, 1]])

솔직히 풀릴 줄 몰랐습니다.
탐색하는 부분에서는 4중 for문이 들어가있기도 하고, 최근 올라온 문제는 제대로 해결하지 못하는게 더 많아 자신없이 코드를 짜고 있었는데, 생각보다 시간도 짧게 나오고 테스트를 모두 통과해 너무 뿌듯했던 경험이었습니다!