(기출 / 구현) 자물쇠와 열쇠

자물쇠와 열쇠

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

프로그래머스

 

---

풀이

해답의 풀이과정은 다음과 같다.

1. 자물쇠 리스트의 크기를 3배로 한다.

2. 4가지 방향으로 돌려본다.

3. 각 방향에서 key의 리스트 값을 더하고 가운데(원래 자물쇠값)가 모두 1을 만족하는 지 확인한다.

=각 수순에 따라 아래 더 자세하게 설명했다.

 

1. 자물쇠 리스트의 크기를 3배로 하는 이유는 아래와 같다.

키의 크기에 맞추어 좀 더 메모리 효율성있게 만들 수 있었지만 항상 m<=n 이기도 하고 이 문제를 반나절동안 잡고 있었더니 넘 힘들어서...(그치만 또 여러번 풀면서 이 방법도 구현해볼 것이다..!!) 0~ 3n-(m-1)의 칸에 캊추어 각 각도에 따라 키를 대보는 방식을 적용해봤다. 

 

2. 아래의 게시물에 2차원 리스트를 90도 돌리는 함수에 대한 설명을 적어두었다.

https://star-ccomputer-go.tistory.com/31

2차 리스트를 돌리기(rotate_a_matrix_by_90_degree())

 

3. 각 방향에서 key의 리스트 값을 더하고 가운데(원래 자물쇠값)가 모두 1을 만족하는 지 확인하기 위해 check 함수를 따로 구현했다.

 

 

---

코딩

def tun(key):
    n = len(key)
    m = len(key[0])
    new_key = [[0]*n for _ in range(m)]
    for i in range(n):
        for j in range(m):
            new_key[j][n-1-i] = key[i][j]
    return new_key

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


def solution(key, lock):
    answer = False
    m = len(key)
    n = len(lock)
    new_lock_len = 3*n
    new_lock = [[0]*(new_lock_len) for _ in range(new_lock_len)]
    for i in range(n):
        for j in range(n):
            new_lock[i+n][j+n] = lock[i][j]

    for _ in range(4):
        key = tun(key)
        for x in range(new_lock_len-(m-1)):
            for y in range(new_lock_len-(m-1)):
                for i in range(m):
                    for j in range(m):
                        new_lock[x+i][y+j] += key[i][j]
                if check(new_lock) == True:
                    answer =  True
                    return answer
                for i in range(m):
                    for j in range(m):
                        new_lock[x+i][y+j] -= key[i][j]

    return answer

key = [[0, 0, 0], [1, 0, 0], [0, 1, 1]]
lock = [[1, 1, 1], [1, 1, 0], [1, 0, 1]]
print(solution(key, lock))