[Python][2020 KAKAO] 프로그래머스 - 자물쇠와 열쇠(LEVEL3)

문제출처 - https://programmers.co.kr/learn/courses/30/lessons/60059

프로그래머스

# 90도 회전
def rotation(arr):
    n = len(arr)
    ret = [[0] * n for _ in range(n)]

    for i in range(n):
        for j in range(n):
            ret[j][n-1-i] = arr[i][j]
    return ret

# 자물쇠가 열리는지 췍
def check(startX, startY, key, lock, expendSize, start, end):
    expendList = [[0] * expendSize for _ in range(expendSize)]

    # expendList에 key 추가
    for i in range(len(key)):
        for j in range(len(key)):
            expendList[startX + i][startY + j] += key[i][j]

    # expendList에 lock 추가하면서 기존 값이랑 더하기
    for i in range(start, end):
        for j in range(start, end):
            expendList[i][j] += lock[i - start][j - start]
            if expendList[i][j] != 1:
                return False

    return True

def solution(key, lock):
    start = len(key) - 1  # expendList에서 lock의 시작 지점
    end = start + len(lock)  # expendList에서 lock이 끝나는 지점
    expendSize = len(lock) + start * 2  # expendList 배열의 크기

    # lock은 고정이고 key가 움직이는거!!!
    for a in range(0, 4):
        for i in range(end):
            for j in range(end):
                if check(i, j, key, lock, expendSize, start, end):
                    return True
        key = rotation(key)

    return False

설명

 

0	0	0	0	0	0	0
0	0	0	0	0	0	0
0	0	1	1	1	0	0
0	0	1	1	0	0	0
0	0	1	0	1	0	0
0	0	0	0	0	0	0
0	0	0	0	0	0	0

(녹색 배열은 key, 빨간색 배열은 lock임)

 

위의 2차원 배열은 (len(key) - 1) * 2 + len(lock) 크기의 배열이다.

 

이 배열을 expendList라고 부르겠음!

 

expendList는 key를 lock의 (0, 0)부터 돌리면서 하나하나 맞춰보기 위해 필요한 배열이다.

 

사실 expendList는 lock 배열을 (len(key) - 1) * 2 + len(lock) 크기만큼 확장한 배열이라고 할 수 있다.

 

lock 배열을 expendList 정가운데 두고 key를 expendList의 (0, 0)부터 돌리면서 열리는지 확인하는 것이다.

 

 

Flow는 다음과 같다.

 

1. expendList의 (0, 0)부터 반복문을 돌리면서 자물쇠가 열리는지 체크한다.

 

2. key 배열을 회전하지 않고 열리면 개꿀이고 안열리면 key 배열을 90도 회전해서 1번을 다시 진행한다.

 

사실 이게 다임

 

lock 배열을 확장한다는 개념만 알고 있으면 간단했던 문제였다..

---

+α

 

배열 회전 하는 방법!!!

 

규칙이 있음 (90도 회전하는 경우)

 

1. 회전 후 배열의 X 인덱스 == 회전하기 전 배열의 Y 인덱스

2. 회전 후 배열의 Y 인덱스 == (배열 크기 - 1) - 회전하기 전 배열의 X 인덱스

 

 

참고 | https://jay-ji.tistory.com/41