[ 프로그래머스 ] 자물쇠와 열쇠 파이썬python 풀이

 

 

// 문제 요약

 

돌려서 끼워 넣을 수 있는 M x M 열쇠가 있을때

 

돌릴 수 없는 N x N 의 자물쇠가 열리는지 안열리는지 확인해라.

 

단, 자물쇠의 열림 조건은 모든 값이 1 이되는가 이다.

 

 

// 풀이

 

전형적인 브루투스 포스 (전체 탐색) 문제.

 

특히 N과 M 이 3 이상이면서 20을 넘지 않는 수로 주어지므로

 

충분히 for문을 여러번 사용해도 되는 문제라고 할 수 있다.

 

 

고고학자 튜브가 나와서 유치원생 문제처럼 그림을 그려놓았지만

 

사실은 복잡한 여러겹의 루프를 적절한 단위의 테스크로 나누고

 

각각 모듈화하여 조합할 수 있는가를 묻는 문제이고

 

최근 딥러닝 프레임워크들이 지향하는 바를 이해하고 구현할 수 있는가

 

물어보는 느낌도 받았다. 특히 Convolution생각이 많이 났다.

 

열쇠를 돌리는 과정에서는 이미지를 간단하게 조작할 수 있는가를 물어보는 것이었고

 

이건 데이터 오그멘테이션과 연관이.... 뇌절같으니 그만하자...

 

 

이런걸 다 차치하더라도 리스트 안에 리스트가 있을경우

 

파이썬에서의 카피를 정확하게 이해하고 원소를 다룰 수 있는가 하는 것을 요구하는

 

이론적으로는 상당히 난이도 있는 문제였다.

 

numpy에 익숙한 사람이라면 오히려 살짝 애 먹을 수도 있는 문제.

 

또 True or False 문제이므로 그냥 때려맞춰도 절반의 결과가 맞았다고 나오는

 

정말 기가차는 문제였다. 버그가 발생하면 시험중엔 디버깅이 거의 불가능한 수준.

 

이 문제에서 요구하는 파이썬의 핵심개념인 call by object-reference 를

 

아래의 글에 정리해 두었다. 참고하길 바란다.

2021.06.02 - [삽질/Python] - [ Python 삽질 ] List의 원소가 한번에 다 바뀔때 deep copy? shallow copy?

[ Python 삽질 ] List의 원소가 한번에 다 바뀔때 deep copy? shallow copy?

우선 코드 전문을 보자.

 

def solution(key, lock):
    M = len(key)
    N = len(lock)

    def list_copy(double_list, i_range, j_range):
        # for the deep copy with an arbitrary range
        result = []
        for i in range(*i_range):
            row = []
            for j in range(*j_range):
                row.append(double_list[i][j])
            result.append(row)
        return result

    def rotate(key):
        _key = []
        for j in range(M):
            _row = []
            for i in range(len(key) - 1, -1, -1):
                _row.append(key[i][j])
            _key.append(_row)
        return _key

    def pad(lock):
        pad_size = N + 2 * (M - 1)
        # "pad = [[0] * pad_size] * pad_size" is wrong (it is a just shallow copy) !!!
        pad = [[0] * pad_size for _ in range(pad_size)]
        lock_start = (M - 1)
        for i in range(N):
            for j in range(N):
                pad[lock_start + i][lock_start + j] = \
                    lock[i][j]
        return pad

    def overlay(start_i, start_j, padded, key):
        len_pd = len(padded)
        # it must be the deep copy
        _padded = list_copy(padded, (0, len_pd), (0, len_pd) )
        for i in range(M):
            for j in range(M):
                _padded[start_i + i][start_j + j] += key[i][j]
        return _padded

    def check(key_on_lock):
        # 2 is not the correct answer.
        for i in range(N):
            for j in range(N):
                if key_on_lock[i][j] != 1:
                    return False
        return True

    def stride_and_check(padded, key):
        for i in range(len(padded) - (M - 1)):
            for j in range(len(padded) - (M - 1)):
                key_on_lock = overlay(i, j, padded, key)
                key_on_lock = list_copy(
                                key_on_lock,
                                ((M - 1), (M - 1) + N),
                                ((M - 1), (M - 1) + N)
                                )
                if check(key_on_lock):
                    return True
        return False

    for _ in range(4):
        key = rotate(key)
        padded = pad(lock)
        if stride_and_check(padded, key):
            return True
    return False

 

많은 사람들이 이런 식의 풀이를  할때

 

문제에서 요구하는 solution 함수와 같은 indentation에 여러 함수들을 나열하는데

 

그렇게 해도 상관없지만

 

팀웍이나 코웍을 하는 경우 개발단계에서 와일드카드(*) 로 import 해 둔 경우에는

 

내가 수정한 파일이 전체 코드에 영향을 크게 줄 수 있으므로

 

굳이 외부에 노출하지 않아도 되는 함수들은

 

함수안에 선언함으로 전체적인 안정성을 주는 것이 더 좋다고 생각한다.

 

 

특별히 주의해야 할 점을 3가지 말하면

 

1. 각각의 copy 과정에서 반드시 모든 리스트를 deep copy 해야만 한다.

2. key가 4회 rotate 되는동안 계속해서 덮어쓰기 되어야 한다.

3. lock의 빈공간이 없더라도 key와 겹치는 부분이 생기면 자물쇠를 열 수 없다.

 

이 부분만 주의하면 꼼꼼하게 풀어볼만한 문제였다.