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

프로그래머스 Lv3 자물쇠와 열쇠 문제입니다.

 

해당 문제 링크의입니다.

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

 

문제의 골자는 2차원 배열을 회전시키고 이동시켜 조건에 맞는 case가 존재하는 지를 탐사하는 것입니다. 

 

전 해당 문제를 2차원 배열을 생성하는 방식이 아닌, 비교해야 할 값만을 따로 모아 배열을 만들고, 배열에 해당하는 원소들을 비교하는 식으로 하였습니다.

 

다음은 제가 풀이한 코드입니다.

def solution(key, lock):
    lk, ll = len(key), len(lock)
    holes = list()
    up = list()
    for i in range(ll):  # 채워줄 것들
        for j in range(ll):
            if lock[i][j] == 0:
                holes.append((i, j))

    for i in range(lk):  # 채울 것들
        for j in range(lk):
            if key[i][j] == 1:
                up.append((i, j))

    for _ in range(4):  # 4번 회전
        for g1 in range(-ll+1, ll):  # 회전이동
            for g2 in range(-ll+1, ll):
                check = [(i[0]+g1, i[1]+g2) for i in up]  # 움직여준 key
                for c in holes:
                    if c not in check:  # 못 채워주면
                        break
                else:
                    for c in check:
                        if c not in holes and 0 <= c[0] < ll and 0 <= c[1] < ll:
                            break
                    else:
                        return True
        # key를 회전시킴 # x, y >> y, n-1-x [2][0] > [0][0]
        up = [(i[1], lk - i[0] - 1) for i in up]
    return False

holes에 key를 이용해 채워줘야 하는 좌표들을 받아주고, up을 통해 key가 채울 수 있는 좌표들을 받아줍니다. 그리고 나서, 평행 이동과 회전 이동을 시켜주며 하나씩 비교해 나가는 방식입니다. 만약 모든 hole을 채울 수 있다면, 추가로 key에서 혹시 hole이 존재하는 위치에 겹쳐지는 부분이 있는 지를 확인합니다. 

 

회전이동을 할 때에는, x, y를 기준으로 y, len-1-x로 이동된다는 사실을 이용하였습니다.