[PG/Python] 자물쇠와 열쇠

📌 문제

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

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

 

📌 문제 접근 방법

1. 자물쇠의 홈을 lock_down에 저장해주었다. 이 때, 가장 먼저 만나게 되는 인덱스를 기준으로 나머지 홈들과의 행, 열방향 거리를 저장해주었다. (가장 먼저 만나게 되는 홈을 기준으로 상대적 위치를 저장)
2. 테스트 케이스 2, 4, 12번에서 자꾸 런타임 에러가 났는데, 이건 도저히 모르겠어서 질문하기를 참고해보니 자물쇠의 모든 값이 1인 경우였다. 이 경우 lock_down이 비어있어서 밑에서 런타임 에러가 나는 것 같았다. 자물쇠의 모든 값이 1인 경우 항상 자물쇠를 열 수 있으므로 바로 True를 리턴해줬다.
3. 열쇠의 돌기는 key_up에 저장해주었다.
4. for문을 4번 돌려서 (90도씩 4번 회전하면 원래대로 돌아오므로) 열쇠의 돌기 위치에 lock_down의 거리를 빼주었다.
   이렇게 하면 현재 보고있는 열쇠의 돌기에서 자물쇠의 홈을 맞추기 위해 필요한 돌기들의 위치를 탐색하게 되는데, 모든 값이 key_up에 포함되어 있다면 우선 열쇠의 돌기와 자물쇠의 홈이 맞게 된다.
5. 자물쇠의 홈과 열쇠의 돌기가 모두 맞았다면, 자물쇠의 홈과 맞지 않는 열쇠의 돌기가 자물쇠의 돌기와 겹치는 지 확인해야 한다. 이 조건을 생각하지 않아서 테스트 케이스 23, 25, 33번을 틀렸다.
6. 모든 조건에서 걸리지 않는다면 True를 리턴하고 조건에서 걸리면 key_up을 90도 돌려서 다시 확인한다.
7. 4번을 돌려서 확인했음에도 조건에 걸리게 되면 결국 False를 리턴한다.

 

📌 코드

def solution(key, lock):
    N = len(lock)
    M = len(lock)
    
    def turn(place):
        new = []
        for i, j in place:
            new.append((j, M-1-i))
        return new
        
        
    lock_down = []
    flag = True
    for i in range(N):
        for j in range(N):
            if lock[i][j] == 0:
                if flag:
                    si = i
                    sj = j
                    flag = False
                    continue
                lock_down.append((si-i, sj-j))
    
    if not lock_down:
        return True
    
    key_up = []
    for i in range(len(key)):
        for j in range(len(key)):
            if key[i][j] == 1:
                key_up.append((i, j))
    
    for _ in range(4):
        for ki, kj in key_up:
            temp = [(ki, kj)]
            for di, dj in lock_down:
                if (ki-di, kj-dj) not in key_up:
                    break
                temp.append((ki-di, kj-dj))
            else:
                rest_key = list(set(key_up)-set(temp))
                for ri, rj in rest_key:
                    if si-N < ki-ri <= si and sj-N < kj-rj <= sj and (ki-ri, kj-rj) not in lock_down:
                        break
                else:
                    return True
        
        key_up = turn(key_up)
    
    return False