[Programmers] 열쇠

🔦 문제 링크

✍️ 풀이

---

• 브루트포스 문제

문제의 핵심은 열쇠에 맞출 자물쇠를 확장시키는 아이디어다. 이를 통해 열쇠의 일부분도 쉽게 자물쇠와 맞춰볼 수 있다.열쇠를 90도로 돌려보면서 가능한 모든 열쇠의 위치를 시도해보고 맞으면 True 모두 안되면 False를 반환한다.

🛠 코드

---

def rotation_90_degree(arr):
    li = []
    for j in range(len(arr)):
        tmp = []
        for i in range(len(arr)-1,-1,-1):
            tmp.append(arr[i][j])
        li.append(tmp)
    return li

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


def solution(key, lock):
    key_l = len(key)
    lock_l = len(lock)

    new_lock = [[0]*(lock_l*3) for _ in range(lock_l*3)]

    for i in range(lock_l):
        for j in range(lock_l):
            new_lock[lock_l + i][lock_l + j] = lock[i][j]

    for _ in range(4):
        key = rotation_90_degree(key)
        for x in range(2*lock_l):
            for y in range(2*lock_l):
                # x, y 시작 위치
                for i in range(key_l):  # key의 길이만큼
                    for j in range(key_l):
                        new_lock[x + i][y + j] += key[i][j]

                if check(new_lock):
                    return True

                for i in range(key_l):
                    for j in range(key_l):
                        new_lock[x + i][y + j] -= key[i][j]
    return False

📝 정리

---

처음에는 아예 자물쇠 확장이라는 생각을 못해서 못풀었고 두번째 풀 때는 몇가지 오류를 범했다.

1. length를 key와 lock을 구분하지 않고 써서 틀림 ( 두 가지 길이 구분 )
2. 한번 맞춰본 key와 lock을 다시 돌려 놓지 않아서 틀림 ( 원상 복구)
3. 똑같이 돌기인 부분은 1 + 1 = 2 이므로 맞지 않는 열쇠임을 생각하지 않았다. ( 문제 읽기 )

🎈 참조

---