문제 출처 프로그래머스

자물쇠와 열쇠

문제 프로그래머스

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def check(lock):
    l_=len(lock)//3
    for i in range(l_, l_*2):
        for j in range(l_, l_*2):
            if lock[i][j] != 1: return False
    return True

def rotate_90(m):
    N = len(m)
    ret = [[0] * N for _ in range(N)]

    for r in range(N):
        for c in range(N):
            ret[c][N-1-r] = m[r][c]
    return ret

def solution(key, lock):
    m=len(key)
    n=len(lock)
    
    big_lock=[[0]*n*3 for _ in range(n*3)]
    for i in range(n):
        for j in range(n):
            big_lock[i+n][j+n]=lock[i][j]
    for rotate in range(4):
        key = rotate_90(key)
        for x in range(n*2):
            for y in range(n*2):
                for i in range(m):
                    for j in range(m):
                        big_lock[x+i][y+j] += key[i][j]

                if check(big_lock) == True: return True
                for i in range(m):
                    for j in range(m):
                        big_lock[x+i][y+j] -= key[i][j]
    
    return False

로직은 생각보다 간단하지만, 문제에 대한 이해가 어려울 수 있다. (내가 오래 걸렸다)

자물쇠와 열쇠에 대한 이해가 필요한데, 열쇠를 회전, 이동하여 자물쇠에 맞춰지면 true, 아니면 false를 반환한다.

그런데 자물쇠나 열쇠나 2차원 배열로 만들어져 있으므로 회전, 이동, 체크(맞춰지는지)에 대한 알고리즘이 필요하다. 우선 2차원 배열에 대한 회전은 로직은 대충 생각나서 구글링으로 찾은 코드를 그대로 넣었다.

이제 이동과 검사를 어떻게 할 것이냐가 문제인데 lock 배열이 3x3 배열이라면 3배씩 확장시켜 0으로 초기화된 9x9 배열로 만들고 중간에 자물쇠 원본(3x3)을 넣는다. 그런 다음 열쇠를 [0][0]부터 차례로 움직이며 9x9의 자물쇠 배열에 더하여 중간 부분이 모두 더해서 1이 되었는지 검사하면 된다.

1
2
3
4
5
6
def check(lock):
    l_=len(lock)//3
    for i in range(l_, l_*2):
        for j in range(l_, l_*2):
            if lock[i][j] != 1: return False
    return True

이 check 함수가 확장되어 key와 더해진 lock 배열의 중앙 부분을 검사하는 함수이다. 이 문제는 for loop에서 범위를 설정하기가 까다로웠다고 생각한다.

또한 코드를 보면 5개나 되는 for loop로 둘러쌓인 것을 알 수 있는데, m, n의 범위는 최대 20이므로 시간복잡도보다는 구현에 초점을 둔 것을 알 수 있다.