[이코테] 구현 - 자물쇠와 열쇠

 

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

하단의 프로그래머스 링크를 참조하자.

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

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

사고과정

• 매우 어려웠..다.. 시간에 구애받지 않고 최대한 아이디어를 생각해보려 했다. 문제를 파악하고 입출력 예시를 이해하는 데만 10분이걸렸다. 주어진 데이터 범위도 적어서 완전 탐색일 것을 예상했다. 그리고 열쇠가 회전, 이동을 할 수 있다는데 회전 -> 이동 인지 이동 -> 회전 순으로 구현해야 하는지 명확히 잘 몰랐다. 어차피 열쇠의 모든 배열이 다같이 이동을 해야하기도 하고 방향은 4번 돌면 다시 원래대로 돌아오니까 회전 -> 이동 순으로 구현해야 겠다고 생각했다. 그리고 이동을 어떻게 시켜야할지.. 재귀함수? DFS?를 이용해야 하는건지 감이 오지 않았다. 그래서 결국 풀이 염탐행..
• 해당 문제를 해결하기 위한 핵심 아이디어들은 다음과 같다.
  1. 열쇠를 -> 자물쇠에 끼워맞추면서 맞는지 아닌지 체크하는 방식. 이 때, 자물쇠의 영역을 넘어가도 된다는 문제 조건 때문에, 자물쇠의 크기를 주어진 범위에서 3배로 크기를 늘렸음.
  2. 늘린 자물쇠에 열쇠를 맞추기 위해서 for loop를 돌 때, 늘린 자물소의 2배 범위까지만 loop를 돌림. 이는 직접 연습장에 그려보면 알게 되는데, 자물쇠 늘린 길이의 최대 인덱스가 원래 자물쇠 길이*3 - 1이기 때문에 자물쇠 길이를 감안하면 2배 범위까지만 돌아야 함(이 아이디어를 현장에서 떠올릴 수 있을까 과연... 싶었다...)
  3. 열쇠를 이동하면서 자물쇠와 맞아떨어진다면, 그 겹치는 범위 즉, 자물쇠의 구역 모든 리스트의 원소가 1이어야만 맞아떨어지는 것이다. 한 개라도 1이 아니면 맞아떨어지지 않는다는 것으로 해석하는 게 매우 인상적이었음..
• 참고로 2차원 리스트를 90도 회전시키는 방식은 팀 노트에 기록해놓자..

풀이(스스로 못 푼 풀이)

# 2차원 리스트를 90도 회전하는 함수
def rotate_matrix_by_90_degree(a):
    n = len(a)  # 행
    m = len(a[0])  # 열
    # 90도 회전한 후 결과값 다음 2차원 리스트(행, 열 Transpose)
    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]  # n=행의 개수
    return result


def check(new_lock):
    origin_lock_len = len(new_lock) // 3
    for i in range(origin_lock_len, origin_lock_len * 2):
        for j in range(origin_lock_len, origin_lock_len * 2):
            if new_lock[i][j] != 1:
                return False
    return True


def solution(key, lock):
    n = len(lock)
    m = len(key)
    # 자물쇠 길이를 3배로 늘리기
    new_lock = [[0] * (n * 3) for _ in range(n * 3)]
    # 늘린 자물쇠에 원래 자물쇠 값 갱신
    for i in range(n):
        for j in range(n):
            new_lock[i + n][j + n] = lock[i][j]  # 이때, n = 원래 자물쇠 길이

    # 4가지 방향에 대해 탐색
    for _ in range(4):
        key = rotate_matrix_by_90_degree(key)  # 열쇠 90도 회전
        # 회전시킨 열쇠를 자물쇠의 중앙부분에 합치기
        for x in range(n * 2):
            for y in range(n * 2):
                # 열쇠 끼우기
                for i in range(m):
                    for j in range(m):
                        new_lock[x + i][y + j] += key[i][j]

                # 열쇠 돌기랑 자물쇠 홈이 맞는지 체크
                if check(new_lock):
                    return True

                # 안맞는 열쇠는 다시 빼기
                for i in range(m):
                    for j in range(m):
                        new_lock[x + i][y + j] -= key[i][j]

    return False