[프로그래머스] 자물쇠와 열쇠(python) - 2020 카카오 신입 공채

문제 바로가기(프로그래머스)

 

아이디어 : 구현(완전탐색), 2차원 리스트 회전

배열을 회전, 이동시켜야 한다는 부분에서 턱 막힌 문제였다. 회전 관련 부분은 따로 다뤘었고, 이동 문제는 배열을 직접 이동시킬 게 아니라, 기본 Lock 배열판을 크게 만들면 되는 거였다. 문제에서 제시한 자물쇠와 열쇠의 크기는 최대 20 x 20 이므로 완전 탐색을 이용해서 열쇠를 이동이나 회전시켜서 자물쇠에 끼워보는 작업을 전부 시도해봐도 무리가 없다. (400 * 400 = 16만, 일반적인 채점 환경에서는 1초에 2000만 ~ 1억 정도의 연산 처리 가능) 즉, 완전 탐색 아이디어를 사용하면 된다. 그리고 완전탐색을 수월하게 하고자 자물쇠 리스트의 크기를 3배 이상으로 변경하면 계산이 수월해진다. 그리고 그 중앙에 실제 자물쇠 크기를 넣으면 된다.

 

또 하나의 아이디어는 키가 자물쇠의 모든 홈을 채울 수 있는지 확인하는 것으로, 모든 자물쇠 칸에 대해 자물쇠 + 열쇠 = 1 인지를 체크하면 된다. 효율적인 코드작성을 위해 키 회전함수인 rotate_2d와 자물쇠의 모든 홈을 채웠는지 확인하는 check함수를 따로 선언했다.

 

def rotate_2d(list_2d):
    n = len(list_2d) # 행 길이 계산
    m = len(list_2d[0]) # 열 길이 계산
    new = [[0] * n for _ in range(m)]
    for i in range(n):
        for j in range(m):
            new[j][n - i - 1] = list_2d[i][j]
    return new

def check(new_lock):
    n = len(new_lock) // 3
    for i in range(n, n * 2):
        for j in range(n, n * 2):
            if new_lock[i][j] != 1:
                return False
    return True

def solution(key, lock):
    n = len(lock)
    m = len(key)
    new_lock = [[0] * (n * 3) for _ in range(n * 3)]
    # 새로운 자물쇠의 중앙에 기존의 자물쇠 넣기
    for i in range(n):
        for j in range(n):
            new_lock[n + i][n + j] = lock[i][j]
    
    # 4번의 회전 key 모두 확인
    for rotate in range(4):
        key = rotate_2d(key)
        # 전체 new_lock과 key 비교하며 찾기
        for x in range(n * 2):
            for y in range(n * 2):
                # key가 겹쳐진 부분에 대해 new_lock + key
                for i in range(m):
                    for j in range(m):
                        new_lock[x + i][y + j] += key[i][j]
                # 자물쇠의 중간부분이 1인지 체크
                if check(new_lock):
                    return True
                # new_lock - key
                for i in range(m):
                    for j in range(m):
                        new_lock[x + i][y + j] -= key[i][j]
    return False