[프로그래머스] 자물쇠와 열쇠 (python)

 

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

프로그래머스

 

def solution(key, lock):
    answer = False
    n = len(lock)
    new_lock = [[0] * 3 * n for _ in range(3 * n)]
    for i in range(n):
        new_lock[i + n] = [0] * n + lock[i] + [0] * n

    match = 0
    for _ in range(4):
        # key + new_lock
        result = [item[:] for item in new_lock]
        for dx in range(1, 2 * n):  # 0~2n
            for dy in range(1, 2 * n):  # 0~2n
                for i in range(len(key)):
                    for j in range(len(key)):
                        result[i + dx][j + dy] += key[i][j]
                # 확인
                if check_key_and_lock(result, n):
                    return True
                result = [item[:] for item in new_lock]
        key = rotate_a_matrix_by_90_degree(key)

    return answer


def check_key_and_lock(result, n):
    for i in range(n, 2 * n):
        for j in range(n, 2 * n):
            if result[i][j] != 1:
                return False
    return True


# 2차원 리스트를 시계빙향(오른쪽) 90도 회전한 결과를 반환하는 함수
def rotate_a_matrix_by_90_degree(a):
    n = len(a)  # 행 길이 계산
    m = len(a[0])  # 열 길이 계산
    result = [[0] * n for _ in range(m)]
    for i in range(n):
        for j in range(m):
            result[j][n - i - 1] = a[i][j]
    return result

 

1. lock 배열을 3배 확장한 new_lock 배열을 만든다.

2. key를 회전시키면서

3. key와 new_lock을 합친다. 합치는 지점은 (1,1) 부터 (2n-1, 2n-1)까지

4. 합쳐서 만든 result 배열을 check_key_and_lock함수를 이용해 기존 lock배열 부분이 모두 1인지 확인한다.

5. 만약 모두 1인 지점이 나온다면 true를 반환하고

6. 아니라면 그 다음 계산을 계속해서 끝까지 true가 없으면 false를 반환한다.

 

복잡하다 복잡해 ...

일단 2차원 리스트를 90도 회전하는 함수는 외워둬야 할 것 같다.

그리고 key랑 new_lock배열을 합치는 부분은 4중반복문이라 효율성이 좋은 코드같지는 않다.

그래서 처음에는 (0,0)~ 부터 시작하는 걸로 제출했을 때에는 딱 1개의 테스트가 시간초과로 실패했는데,

(1,1)~로 바꾸고 혹시나 싶어 다시 제출했을 때 모두 성공했다. 그래도 오래 걸리는 코드인듯

 

리스트를 복사해오는 방식은 deepcopy와 slicing 방법이 있다고 하는데,

deepcopy가 더 느리다고 한다. 처음에는 result 에 new_lock을 복사할 때 deepcopy를 썼는데 slicing 방식으로 바꿔서 제출하니 속도가 훨씬 빨라졌다.

[파이썬] 리스트의 깊은복사는 deepcopy가 빠를까? slicing이 빠를까?

 

그리고 lock배열을 3배 확장시키는 아이디어는 [이취코]책에서 참고했다.

아직 구현 문제는 문제이해-아이디어-구현 까지 혼자 힘으로 하기 어려운 것 같다..ㅠ

 

나는 새로운 배열 리스트에 기존 배열을 복사한 뒤에 키값을 더하고, 다시 배열을 초기화하는 방식을 사용했는데

책에서는 키를 자물쇠에 꽂은 뒤에 다시 빼줌으로써 리스트 복사를 할 필요가 없는 방식을 사용했다.

이 방법도 괜찮은 것 같아서 책에서 나온 코드를 참고해서  수정해보았다.

 

def solution(key, lock):
    n = len(lock)
    new_lock = [[0] * 3 * n for _ in range(3 * n)]
    for i in range(n):
        new_lock[i + n] = [0] * n + lock[i] + [0] * n

    match = 0
    for _ in range(4):
        key = rotate_a_matrix_by_90_degree(key)
        # key + new_lock
        for dx in range(1, 2 * n):  # 0~2n
            for dy in range(1, 2 * n):  # 0~2n
                for i in range(len(key)):
                    for j in range(len(key)):
                        new_lock[i + dx][j + dy] += key[i][j]
                # 확인
                if check_key_and_lock(new_lock, n):
                    return True
                # 자물쇠에서 열쇠를 다시 빼기
                for i in range(len(key)):
                    for j in range(len(key)):
                        new_lock[i + dx][j+ dy] -= key[i][j]
        
    return False


def check_key_and_lock(result, n):
    for i in range(n, 2 * n):
        for j in range(n, 2 * n):
            if result[i][j] != 1:
                return False
    return True


# 2차원 리스트를 시계빙향(오른쪽) 90도 회전한 결과를 반환하는 함수
def rotate_a_matrix_by_90_degree(a):
    n = len(a)  # 행 길이 계산
    m = len(a[0])  # 열 길이 계산
    result = [[0] * n for _ in range(m)]
    for i in range(n):
        for j in range(m):
            result[j][n - i - 1] = a[i][j]
    return result