프로그래머스 - 자물쇠와 열쇠 [Python]

 문제

 

programmers.co.kr/learn/courses/30/lessons/60059

코딩테스트 연습 - 자물쇠와 열쇠

 

 문제 상황

 

- 자물쇠와 열쇠의 배열이 주어지고 해당 열쇠를 90도씩 돌려가며 자물쇠와 매칭시켜 맞는 순간이 존재하면 True를, 없으면 False를 출력한다.

 

 

 

 해결 전략

 

- 범위가 크지 않으므로 완전탐색으로 모든 상황을 확인한다.

 

 

 

 코드

 

import copy
# 90도 회전
def rotate(ndarray):
    result = [[0 for _ in range(len(ndarray))] for _ in range(len(ndarray))]
    for i in range(len(ndarray)):
        for j in range(len(ndarray)):
            result[j][len(ndarray)-1-i] = ndarray[i][j]
    return result 
 
# 해당 key로 board를 돌았을 때 열리면 True, 아니면 False를 반환한다.
def check(key, board, N, M, i, j):
    # key를 기준으로 움직이며 board와 겹치는 부분을 갱신해준다.
    for x in range(N):
        for y in range(N):
            board[x+i][y+j] = (board[x+i][y+j]^key[x][y])
    # 결과 보기
    for x in range(N-1,N+M-1):
        for y in range(N-1,N+M-1):
            if board[x][y] == 0:
                return False
    return True
 
def solution(key, lock):
    # lock을 더 넓은 판으로 만들어준다. 
    N, M = len(key), len(lock)
    origin_board = [[0 for i in range(2*N+M-2)] for j in range(2*N+M-2)]
    # board의 가운데를 lock으로 만들어준다.
    for i in range(M):
        for j in range(M):
            origin_board[i+N-1][j+N-1] = lock[i][j]
    cnt = 3
    board = copy.deepcopy(origin_board)
    while cnt >= 0:
        # i,j는 각각 row와 col 방향으로 키가 board에서 얼만큼 움직였는지를 의미한다.    
        for i in range(N+M-1):
            for j in range(N+M-1):
                # board에서 key가 i, j 만큼 움직였을 때 board의 가운데 요소가 모두 1이면 열린다.
                if check(key,board,N,M,i,j): return True
                board = copy.deepcopy(origin_board)
        # 만약 안되면 키를 총 3번 회전시켜 다시 해본다.
        key = rotate(key)
        cnt -= 1        
    return False

 

 

 

 해설

 

- 반복문이 많고 상황이 복잡해서 굉장히 복잡해 보이는 문제였다.

 

- 몇가지 상황을 좀 더 쉽게 풀어주는 스킬과 함수의 분리로 풀 수 있었다.

 

 

 

 새로 학습한 것 & 실수 

 

- 어떤 요소를 변경해가며 확인할 때에 반드시 원래대로 복원하는 작업을 해주어야한다. 계속 로직을 따라가기만 하면 계속 변한 상황에서 로직이 일어난다.

 

- 일부분만 확인할 때에는 잘라서 확인하는 것도 가능하지만 그냥 판을 크게 만드는게 훨씬 편할 수 있다.