[python] 프로그래머스 - 자물쇠와 열쇠(2020 KAKAO BLIND RECRUITMENT)

🤔문제 해결

1. lv3 | 완전탐색?

2. 자물쇠 주위를 1과0이 아닌 다른 숫자로 채워준다. ( 열쇠의 길이 - 1 만큼 )

3. 열쇠를 새롭게 만들어진 자물쇠 위에 놓고 2중 for문으로 전부 겹쳐가며 탐색한다.

( 자물쇠를 열쇠의 크기만큼 잘라서 열쇠와 자물쇠를 비교)

( 노란색: 원래자물쇠, 초록색: 새롭게 채워놓은 빈공간, 파란색: 열쇠

4. 열소의 돌기(1)와 자물쇠의 구멍(0)이 만나면 카운트 +1,

열쇠의 돌기(1)와 자물쇠의 돌기(1)가 만나면 탈락,

열쇠의 구멍(0)과 자물쇠의 구멍(0)이 만나면 탈락,

자물쇠의 모든 구멍(0)이 열쇠의 돌기(1)로 채워져야 한다. (즉, 파란영역 안의 자물쇠가 모든 구멍(0)을 가지고 있어야한다)

5. 자물쇠 전체의 구멍의 숫자와 열쇠의 돌기가 자물쇠의 구멍을 만난 수를 비교해서 일치하면 성공, 아니면 다음으로

 

6. 끝까지 탐색 했다면 열쇠를 시계방향으로 90도 회전시켜준다.

그리고 다시 3번부터 반복한다.

 

💨 처음 주변을 채우지않고 어떻게 인덱스를 잘 조정해서 해보려고 했지만 규칙을 찾기가 너무 힘들었다. 주변을 채우는 방법을 생각하고 보니 예전에 풀었던 쉬운 문제와 비슷했다. 이 문제에서는 주변을 채우는 아이디어를 생각하는게 핵심

 

💻소스 코드

from itertools import chain  # 2차원리스트 1차원리스트로 만들기


def solution(key, lock):
    lenK = len(key)
    lenL = len(lock)
    # 자물쇠 주위를 빈공간으로 확장해주기 | 인덱스에러방지 - 이 문제의 핵심
    lock = fillAround(lock, key)

    for i in range(4):  # 최초한번, 90, 180, 270 확인
        if cutLock(key, lock):  # 일치하면 True반환하고 끝
            return True
        else:  # 아니면 key를 회전시킨다.
            key = lotationKey(key)

    return False


# 자물쇠 자르기
def cutLock(key, lock):
    # 자물쇠의 열쇠 구멍 갯수
    holeCnt = list((chain.from_iterable(lock))).count(0)
    lenK = len(key)
    lenL = len(lock) - (lenK * 2 - 2)
    for i in range(lenK + lenL - 1):
        for j in range(lenK + lenL - 1):
            # 자물쇠를 열쇠 크기만큼 자르기
            partOfLock = [row[j:j + lenK] for row in lock[i:i + lenK]]

            # tip: 자른 자물쇠의 구멍이 전체 구멍을 포함할 때만 체크하면 된다!
            if list(chain.from_iterable(partOfLock)).count(0) == holeCnt:
                if checkKey(key, partOfLock, holeCnt):
                    return True
    return False


# 열쇠가 맞는 지 확인
def checkKey(key, partOfLock, holeCnt):
    lenK = len(key)
    cnt = 0
    for i in range(lenK):
        for j in range(lenK):

            if key[i][j] == 1:  # 열쇠 돌기와
                if partOfLock[i][j] == 0:  # 자물쇠 구멍이 만나면 O
                    cnt += 1
                elif partOfLock[i][j] == 1:  # 자물쇠 돌기가 만나면 X
                    return False
            else:  # 열쇠 구멍과
                if partOfLock[i][j] == 0:  # 열쇠 구멍이 만나면 X
                    return False

    if cnt == holeCnt:
        return True

    return False


# 자물쇠의 주위를 채워주기 확인!!
def fillAround(lock, key):
    lenL = len(lock)
    lenK = len(key)
    # 위아래 채우기
    newLock = [[9] * lenL] * (lenK - 1) + lock + [[9] * lenL] * (lenK - 1)
    # 양옆 채우기
    for i in range(len(newLock)):
        newLock[i] = [9] * (lenK - 1) + newLock[i] + [9] * (lenK - 1)

    return newLock


# 열쇠 회전하기 확인!
def lotationKey(key):
    lenK = len(key)
    newKey = [[0] * lenK for _ in range(lenK)]
    for i in range(lenK):
        for j in range(lenK):
            newKey[i][j] = key[lenK - j - 1][i]

    return newKey


print(solution([[0, 0, 0], [1, 0, 0], [0, 1, 1]], [[1, 1, 1], [1, 1, 0], [1, 0, 1]]))

 

📕문제 확인

출처: 프로그래머스

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

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

---

---

---

문제 설명

고고학자인 튜브는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다.

잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.

자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.

열쇠를 나타내는 2차원 배열 key와 자물쇠를 나타내는 2차원 배열 lock이 매개변수로 주어질 때, 열쇠로 자물쇠를 열수 있으면 true를, 열 수 없으면 false를 return 하도록 solution 함수를 완성해주세요.

제한사항

• key는 M x M(3 ≤ M ≤ 20, M은 자연수)크기 2차원 배열입니다.
• lock은 N x N(3 ≤ N ≤ 20, N은 자연수)크기 2차원 배열입니다.
• M은 항상 N 이하입니다.
• key와 lock의 원소는 0 또는 1로 이루어져 있습니다.
  • 0은 홈 부분, 1은 돌기 부분을 나타냅니다.

---

입출력 예

keylockresult

[[0, 0, 0], [1, 0, 0], [0, 1, 1]]

[[1, 1, 1], [1, 1, 0], [1, 0, 1]]

true

입출력 예에 대한 설명

key를 시계 방향으로 90도 회전하고, 오른쪽으로 한 칸, 아래로 한 칸 이동하면 lock의 홈 부분을 정확히 모두 채울 수 있습니다.