[코테 공부] 프로그래머스 자물쇠와 열쇠

배열 인덱싱이 헬이었던 문제.. 결국은 해냈다!

 

처음에 제출했을 때 all pass가 안떠서

90도 회전했을 때, i=3, j=3 위치에서 정확히 true가 뜨는지 디버깅 해보았더니,

엉뚱한 곳에서 true를 계산해 출력하는 것을 확인했다. 

따라서 위와 같은 조건을 만족할 때 true가 뜰때까지 디버깅한 결과, 해결되었다. 

 

array[x:y][x:y] -> numpy를 쓰지 않다보니 이런식으로 인덱싱하는 것을 피할 수 있는 다른 방법을 고안했고,

• key 배열을 각도만큼 회전시킬때, list(zip(*array[::-1]))를 활용한다는 점, 
• 완벽히 배열을 깊게 복사하려면, copy.deepcopy(array) 를 써야 하는 것도 검색을 통해 배웠다. 

import copy

def make_big(n, lock):
    big_n = len(lock) + (n-1)*2
    big_lock = [[0]*big_n for n in range(big_n)]
    
    for i in range(len(lock)):
        for j in range(len(lock)):
            big_lock[i+n-1][j+n-1] = lock[i][j]    
    return big_lock

def rotate_key(key, angle):
    n = angle // 90 
    for i in range(n):
        key = list(zip(*key[::-1]))
    return key

def match_key(i, j, key, lock, lock_n):
    # key를 lock에 더해보기 
    # 더한 후, new_lock에서 실제 lock 자리만 sum 추출.
    lock_sum = 0
    for lx, kx in zip(range(i, i+len(key)), range(len(key))):
        for ly, ky in zip(range(j, j+len(key)), range(len(key))):
            # lock에는 0 또는 1의 숫자가 들어가야 하는 것 주의 
            # 1, 1 끼리는 들어갈 수 없음 주의 
            if lock[lx][ly] + key[kx][ky] == 2:
                return 0
            
            lock[lx][ly] = max(lock[lx][ly], key[kx][ky])
            # print(x, y, lx, ly)
            
    #lock 크기 내 1인 값 모두 더하기
    x, y = len(key)-1, len(key)+lock_n-1
    for lx in range(x, y):
        for ly in range(x, y):
            lock_sum += lock[lx][ly]
            # print(lock_sum, lx, ly)
    # print(key, lock)
    return lock_sum

def solution(key, lock):
    #자물쇠가 최대 20크기라면, 열쇠는 (20+19*2)^2번 탐색
    #완전 탐색이 가능하다고 판단.
    key_n, lock_n = len(key), len(lock)
    big_lock = make_big(key_n, lock)
    big_n = len(big_lock)
    # print(big_lock)
    
    #회전하면서 비교 가능 
    for angle in [0, 90, 180, 270]:
        # if angle != 90 : continue
        new_key = rotate_key(key, angle)
        # print(new_key)
        for i in range(big_n-key_n+1):
            for j in range(big_n-key_n+1):
                # key를 lock에 더해보기 
                # 더한 후, new_lock에서 실제 lock 자리만 sum 추출.
                output = match_key(i, j, new_key, copy.deepcopy(big_lock), lock_n)
                # print(i, j, angle, lock_n**2, output)
                if lock_n**2 == output:
                    return True       
             
    return False