자물쇠와 열쇠 (Level 3)

문제

 

https://school.programmers.co.kr/learn/courses/30/lessons/60059

프로그래머스

 

내 풀이

 

가장 먼저 든 생각은 "자물쇠를 확장하자"였다. 가로와 세로의 길이가 (N + 2*M - 2)인 확장된 자물쇠를 만들어야 한다.

확장된 자물쇠의 중앙에 원래 자물쇠가 있다고 가정했을 때, 자물쇠의 홈의 좌표를 lock_zero에, 자물쇠 돌기의 좌표를 lock_one에 저장하였다.

 

열쇠는 90도 회전이 가능하므로, 열쇠를 90도로 회전하는 함수 rotate를 만들어주었다.

 

그리고 열쇠를 한 칸씩 옮기면서 자물쇠의 홈 set이 열쇠의 돌기 set의 부분집합인지 확인하였다. 부분집합이 맞으면 자물쇠의 모든 홈이 열쇠의 돌기와 딱 맞는다는 뜻이다.

그리고 열쇠의 돌기 set과 자물쇠의 홈 set의 차집합과 자물쇠의 돌기에 교집합이 있는지 확인하였다. 이것은 자물쇠의 돌기와 열쇠의 돌기가 만나는지 아닌지 확인하기 위함이다. 서로 만나면 안 되기 때문이다.

 

열쇠와 자물쇠가 맞아떨어지는지 구하고 열쇠를 90도 회전시키는 것을 반복한다.

중간에 답이 나오면 True를 반환하고, 모든 경우에서 답이 없으면 마지막에 False를 반환하게 된다.

 

def solution(key, lock):
    answer = True
    N, M = len(lock), len(key)
    
    ex_len = N + 2*M - 2
    lock_zero, lock_one = set(), set()
    for i in range(M-1, M-1+N):
        for j in range(M-1, M-1+N):
            if lock[i-(M-1)][j-(M-1)] == 0:
                lock_zero.add((i, j))
            else:
                lock_one.add((i, j))
    
    def rotate(my_key):
        result = []
        for j in range(M):
            temp = []
            for i in range(M-1, -1, -1):
                temp.append(my_key[i][j])
            result.append(temp)
        return result

    for k in range(4):
        for i in range(ex_len - M + 1):
            for j in range(ex_len - M + 1):
                x, y = i, j
                key_one = set()
                for a in range(x, x+M):
                    for b in range(y, y+M):
                        if key[a-x][b-y] == 1: # 열쇠의 돌기
                            key_one.add((a, b))
                if lock_zero.issubset(key_one): # 자물쇠의 홈과 열쇠의 돌기
                    intersect = key_one - lock_zero
                    if not (intersect & lock_one):
                        return True
        key = rotate(key)       
        
    return False

 

다른 풀이

 

신기하게 list(zip(*arr[::-1]))을 사용하면 바로 90도 회전된 배열이 나온다.

 

arr이 [[0, 0, 0], [1, 0, 0], [0, 1, 1]]이라고 하자.

arr = [[0, 0, 0],
         [1, 0, 0],
         [0, 1, 1]]

reversed = arr[::-1]
reversed = [[0, 1, 1], [1, 0, 0], [0, 0, 0]]

2차원 배열의 인자를 zip()으로 묶어준다.
rotated = list(zip(*arr[::-1]))

zip()은 각 인자들을 튜플로 묶어서 반환하기 때문에 list를 이용해 데이터 타입을 다시 바꿔준다.
zip(*arr[::-1]) = [(0, 1, 0), (1, 0, 0), (0, 0, 0)]
rotated = [[0, 1, 0], [1, 0, 0], [0, 0, 0]]

 

수정된 내 풀이

 

def solution(key, lock):
    answer = True
    N, M = len(lock), len(key)
    
    ex_len = N + 2*M - 2
    lock_zero, lock_one = set(), set()
    for i in range(M-1, M-1+N):
        for j in range(M-1, M-1+N):
            if lock[i-(M-1)][j-(M-1)] == 0:
                lock_zero.add((i, j))
            else:
                lock_one.add((i, j))
    
    def rotate(my_key):
        return list(zip(*my_key[::-1]))

    for k in range(4):
        for i in range(ex_len - M + 1):
            for j in range(ex_len - M + 1):
                x, y = i, j
                key_one = set()
                for a in range(x, x+M):
                    for b in range(y, y+M):
                        if key[a-x][b-y] == 1: # 열쇠의 돌기
                            key_one.add((a, b))
                if lock_zero.issubset(key_one): # 자물쇠의 홈과 열쇠의 돌기
                    intersect = key_one - lock_zero
                    if not (intersect & lock_one):
                        return True
        key = rotate(key)       
        
    return False

 

총평

역시 레벨 3는 레벨 3이다.