[프로그래머스] 자물쇠와 열쇠

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

프로그래머스

---

우왕 진짜 어렵다

 

일단 아이디어 자체를 떠올리는 건 아주 크게 어렵지는 않다

그렇지만 이것조차 무지성으로 하면 비효율적이고, 머리를 쓰긴 써야함

 

문제 조건이다.

M과 N이 아주 작은 정수이기 때문에 ,하나하나 다 끼워봐도 시간초과가 나지 않겠다는 생각이 들어야한다.

 

이제부터 문제는 이것을 어떻게 구현할 것인지이다.

---

우선  key를 하나하나 끼워보기 전에, 보다 편하게 하기 위해서

lock 리스트 크기를 3배 확장해준다.

 

<lock: 확장 전>

1	1	1
1	1	0
1	0	1

 

<newLock: 확장 후>

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

 

이 상태에서 열쇠를 회전하거나 옮겨가면서 배열에 끼워맞춰본다.

열쇠를 끼워본 뒤에는 lock에 해당하는 회색 부분의 숫자가 모두 1인지 체크하면 된다.

 

(모두 1이 되면 true를 리턴하고, 그렇지 않으면 열쇠를 회전하거나 옮겨서 다시 끼워보는 작업을 반복)

---

열쇠 회전시키기

#배열 90도 회전시키기
def rotate(arr):
    n, m = len(arr), len(arr[0])
    result = [[0]*n for _ in range(m)]
    for i in range(n):
        for j in range(m):
            result[j][n-i-1] = arr[i][j]
    return result

참고: 2차원배열 오른쪽으로 90도 회전시키기

---

전체 소스코드

#열쇠 회전시키기
def rotate(arr):
    n, m = len(arr), len(arr[0])
    result = [[0]*n for _ in range(m)]
    for i in range(n):
        for j in range(m):
            result[j][n-i-1] = arr[i][j]
    return result

#자물쇠 배열의 값이 모두 정확히 1인지 체크
def check(newLock):
    length = len(newLock)//3
    for i in range(length,length*2):
        for j in range(length,length*2):
            if newLock[i][j] != 1:
                return False
    return True

def solution(key, lock):
    n = len(lock)
    m = len(key)
    
    #자물쇠 배열 3배 확장하기
    newLock = [[0 for j in range(n*3)] for i in range(n*3)]
    for i in range(n,n*2):
        for j in range(n,n*2):
            newLock[i][j] = lock[i-n][j-n]
            
    #key를 4번 회전시키면서 확인
    for rotation in range(4):
        key = rotate(key)
        for x in range(n*2):
            for y in range(n*2):
                #열쇠 껴보기
                for i in range(m):
                    for j in range(m):
                        newLock[x+i][y+j] += key[i][j]
                #열리는지 체크
                if check(newLock) == True:
                    return True
                #열쇠 빼기
                for i in range(m):
                    for j in range(m):
                        newLock[x+i][y+j] -= key[i][j]
                    
    return False

 

출처: 이것이 취업을 위한 코딩테스트다 with 파이썬 (나동빈)