[2020 KAKAO BLIND RECRUITMENT] 자물쇠와 열쇠

내가 푼 풀이

import copy

def setLock(M, N, board, lock):
    for i in range(N):
        for j in range(N):
            board[i+M][j+M] = lock[i][j]

def lotateKey(M, key): #(x, y) -> (y, M - 1 - x), 시계방향으로 90도
    newKey = [[0]*M for _ in range(M)]
    for i in range(M):
        for j in range(M):
            newKey[j][M-1-i] = key[i][j]
    return newKey
   #return list(zip(*key[::-1]))

def putKey(x, y, M, checkBoard, key):
    for i in range(M):
        for j in range(M):
                checkBoard[i + x][j + y] += key[i][j]

def check(M, N, checkBoard):
    for i in range(N):
        for j in range(N):
            if checkBoard[i+M][j+M] != 1:
                return False
    return True

def solve(M, N, key, lock, board):
    for lotate in range(4):
        key = lotateKey(M, key)
        for i in range(1, M+N):
            for j in range(1, M+N):
                checkBoard = copy.deepcopy(board)
                putKey(i, j, M, checkBoard, key)
                if check(M, N, checkBoard):
                    return True
    return False

def solution(key, lock):
    answer = True
    M, N = len(key), len(lock)
    board = [[0] * (M*2 + N) for _ in range(M*2 + N)]
    setLock(M, N, board, lock)
    answer = solve(M, N, key, lock, board)
    return answer

어떻게 풀지 감이 잘 안오던 문제였다. 배열의 크기가 크지 않아 완전탐색으로 구하면 되는 문제였음!

처음에는 checkBoard = board로 설정해서 call by reference방법으로 값이 변경되어서 애먹었었다.

checkBoard = board.copy()
checkBoard = board[:]

이렇게 변경해서 했을때도 checkBoard 내용을 바꾸었을 뿐인데 board까지 같이 바뀌어서 구글링한 결과, 얕은 복사와 깊은 복사에 대해 알게 되었다! copy, 슬라이싱 방법 모두 얕은 복사 방법으로, 새로운 메모리 주소가 부여되지만 그 안에 있는 객체는 같은 주소를 바라보기 때문에 주의해야한다.

💡 리스트 깊은 복사 방법(call by value)

copy.deepcopy()

import copy
checkBoard = copy.deepcopy(board)

내부에 객체들까지 모두 새롭게 copy 되어 내부의 객체를 바꾸어도 원래의 리스트에는 영향을 끼치지 않는다.

💡 파이썬에서는 2차원 리스트 회전을 한 문장으로 할 수 있다!

c++에 익숙한 나같은 사람은 회전했을 때 각 좌표의 규칙성을 이용해서 배열을 회전시켰다.

Like this!

def lotateKey(M, key): #(x, y) -> (y, M - 1 - x), 시계방향으로 90도
    newKey = [[0]*M for _ in range(M)]
    for i in range(M):
        for j in range(M):
            newKey[j][M-1-i] = key[i][j]
    return newKey

파이썬에서는 강력한 함수 zip과 asterisk를 이용해 리스트 회전을 간편하게 할 수 있다.

한문장으로 시계방향으로 90도 돌리기!

key = [[0, 0, 0]
     , [1, 0, 0]
     , [0, 1, 1]]
def lotateKey(key):
    return list(zip(*key[::-1]))

하나씩 뜯어보자.

1. key[ : : -1]

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

key를 -1 간격으로, 즉 한 칸씩 뒤로가면서(=역순으로) 슬라이싱 한 것이다.

2. *key[::-1]

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

*(asterisk)는 unpacking의 역할을 한다

*를 이용해 괄호를 벗길 수 있다. zip 함수에서는 여러 그룹의 데이터를 처리해야하기 때문에 하나의 리스트를 분해시킨 것이다!

3. zip(*key[::-1])

>  (0, 1, 0)
   (1, 0, 0)
   (1, 0, 0)

zip() 함수를 활용하면 여러 그룹의 데이터를 루프를 한 번만 돌면서 처리할 수 있다. 실제로 zip 함수는 이터레이터를 반환하기 때문에 단순히 zip(*key[::-1])을 출력하면 위와 같이 출력되지는 않는다. for문을 통해 해당 이터레이터를 받는 객체를 출력한 결과이다. zip()을 이용하여 각각의 그룹의 인자들을 튜플 형식으로 모았다.

4. list(zip(*key[::-1]))

> [(0, 1, 0)
  ,(1, 0, 0)
  ,(1, 0, 0)]

튜플 형식으로 반환된 것을 list의 형식으로 출력하기 위해 list() 함수를 사용했다.

최종적으로 리스트가 회전된 것을 알 수 있다. 파이썬은 내장함수를 얼마나 잘 이용하는지가 문제 풀 때 속도를 확 줄여줄 수 있는 것 같다.