[ 알고리즘 ] 프로그래머스: 자물쇠와 열쇠

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다.
이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ 프로그래머스 ] 자물쇠와 열쇠를 풀고 작성한 글입니다.

문제

문제 설명

고고학자인 "튜브"는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다.

잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1 인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.

자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.

열쇠를 나타내는 2차원 배열 key와 자물쇠를 나타내는 2차원 배열 lock이 매개변수로 주어질 때, 열쇠로 자물쇠를 열수 있으면 true를, 열 수 없으면 false를 return 하도록 solution 함수를 완성해주세요.

제한사항

• key는 M x M(3 ≤ M ≤ 20, M은 자연수)크기 2차원 배열입니다.
• lock은 N x N(3 ≤ N ≤ 20, N은 자연수)크기 2차원 배열입니다.
• M은 항상 N 이하입니다.
• key와 lock의 원소는 0 또는 1로 이루어져 있습니다.
  • 0은 홈 부분, 1은 돌기 부분을 나타냅니다.

풀이

접근법

배열에 대한 90도 회전의 경우 array[x][y] = array[y][length-1-x] 가 된다.

열쇠가 자물쇠의 크기를 벗어나도 괜찮기 때문에 자물쇠의 크기를 열쇠의 길이인 M-1만큼 상하좌우에 요소가 전부 0인 배열을 추가해서 늘려줘서 반복문을 수행하며 하나씩 더해 나가고 돌기와 돌기가 만나서 값이 2가 되거나 열쇠의 흠이 채워지지 않아 0으로 남아 있는 경우 제대로 열쇠를 열 수 없는 경우이기 때문에 False 를 반환하면 된다.

나의 풀이

접근법을 토대로 문제를 풀면 아래와 같다.

def rotate(key: list[list[int]]) -> list[list[int]]:
    temp: list[list[int]] = [ [0] * len(key) for _ in range(len(key)) ]
    for i in range(len(key)):
        for j in range(len(key)):
            temp[i][j] = key[j][len(key)-1-i]
    
    return temp


def validate_lock(M: int, N: int, new_lock: list[list[int]]) -> bool:
    for i in range(N):
        for j in range(N):
            if new_lock[M-1+i][M-1+j] != 1:
                return False
    
    return True


def solution(key: list[list[int]], lock: list[list[int]]) -> bool:
    M: int = len(key)
    N: int = len(lock)
    new_lock: list[list[int]] = [
        [0] * ((M-1)*2+N) for _ in range((M-1)*2+N)
    ]
    
    for i in range(N):
        for j in range(N):
            new_lock[M-1+i][M-1+j] = lock[i][j]
    
    for _ in range(4):
        for x in range(M-1+N):
            for y in range(M-1+N):
                for i in range(M):
                    for j in range(M):
                        new_lock[i+x][j+y] += key[i][j]
                    
                if validate_lock(M, N, new_lock):
                    return True
                
                else:
                    for i in range(M):
                        for j in range(M):
                            new_lock[i+x][j+y] -= key[i][j]
        
        key = rotate(key)
    
    return False

Big-O

최악의 경우 M과 N의 길이가 같을 때이기 때문에 시간 복잡도는 O(N^4)이다.

기타

2차원 배열을 각각 90도, 180도, 270도를 회전하는 함수는 각각 아래와 같다.

def rotate_90(array: list[list[int]]) -> list[list[int]]:
    x_length: int = len(array)
    y_length: int = len(array[0])

    temp: list[list] = [
        [0] * x_length for _ in range(y_length)
    ]
    for i in range(x_length):
        for j in range(y_length):
            temp[i][j] = array[j][x_length-1-i]

    return temp


def rotate_180(array: list[list[int]]) -> list[list[int]]:
    x_length: int = len(array)
    y_length: int = len(array[0])

    temp: list[list] = [
        [0] * x_length for _ in range(y_length)
    ]
    for i in range(x_length):
        for j in range(y_length):
            temp[i][j] = array[x_length-1-i][y_length-1-j]

    return temp


def rotate_270(array: list[list[int]]) -> list[list[int]]:
    x_length: int = len(array)
    y_length: int = len(array[0])

    temp: list[list] = [
        [0] * x_length for _ in range(y_length)
    ]
    for i in range(x_length):
        for j in range(y_length):
            temp[i][j] = array[y_length-1-j][i]

    return temp