[구현] 자물쇠와 열쇠

2020 카카오 신입 공채 문제다.

 

먼저 2차원 배열을 시계방향으로 90도 회전시키는 함수다.

def rotate_a_matrix_by_90_degree(a):
  n = len(a) # 행 길이 계산
  m = len(a[0]) # 열 길이 계산
  
  # 90도 돌리기 위해서 n, m 위치 변경
  result = [[0] * n for _ in range(m)]

  for i in range(n):
    for j in range(m):
      result[j][n-i-1] = a[i][j]
  
  return result


a = [[0,0], [1,0], [0,1], [0,0]]
# 결과 [[0, 0, 1, 0], [0, 1, 0, 0]]
print(rotate_a_matrix_by_90_degree(a))

 

다음 soultion 함수를 보자. 입력받은 len(key), len(lock) 를 통해 key, lock 배열의 행을 알아낸다. 정사각이므로 열은 따로 구할 필요가 없다. 자물쇠 크기의 3배짜리 배열을 만들고 가운데에 자물쇠를 넣고 나머지는 0으로 만든다. 이중 for문 돌면서 넣는데, 각 인덱스에 n값을 더해줌으로써 가운데에 채워진다.

def solution(key, lock):
    n = len(lock)
    m = len(key)

    # 자물쇠의 크기를 기존의 3배로 변환
    new_lock = [[0] * (n * 3) for _ in range(n * 3)]

    # 새로운 자물쇠의 중앙 부분에 기존의 자물쇠 넣기
    for i in range(n):
        for j in range(n):
            new_lock[i + n][j + n] = lock[i][j]
            
...

 

cf) 자물쇠 영역을 벗어난 부분에 있는 0, 1은 자물쇠를 여는데 영향을 주지 않는다는 조건 때문에 실제 자물쇠 보다 크게 잡는다. 책 대로 3배로 잡으니까 직관적으로 이해하기도 편하고 좋았다. 

 

이제 코드의 하이라이트 부분이다. 90도씩 4방향 모두 돌면서 확인을 하는 로직이다. 5중 for문이나 되지만 n과 m이 최대 20까지라서 완전탐색이 문제 없는거 같다.

    # 4가지 방향에 대해서 확인
    for rotation in range(4):
        key = rotate_a_matrix_by_90_degree(key) # 열쇠 회전
        for x in range(n * 2):
            for y in range(n * 2):
                # 자물쇠에 열쇠를 끼워 넣기
                for i in range(m):
                    for j in range(m):
                        new_lock[x + i][y + j] += key[i][j]
                # 새로운 자물쇠에 열쇠가 정확히 들어 맞는지 검사
                if check(new_lock) == True:
                    return True
                # 자물쇠에서 열쇠를 다시 빼기
                for i in range(m):
                    for j in range(m):
                        new_lock[x + i][y + j] -= key[i][j]
    return False

 

new_lock 크기가 3배가 됐으니 인덱스 움직임은 2배에 해당하는 수까지만 돌아야 한다. 예를들어 n이 3이라면 new_lock 크기는 9x9 배열이고 이중 for문으로 하나씩 순회할 때 0~5(6개)까지만 돌아야 나머지 6,7,8 인덱스도 딱 채워진다.

 

그리고 그 밑에 0부터 m까지 이중 for문을 돌면서 rotate_a_matrix_by_90_degree 함수를 통해 회전된 key 값을 new_lock 에 더한다.

for x in range(n * 2):
  for y in range(n * 2):
    # 자물쇠에 열쇠를 끼워 넣기
      for i in range(m):
        for j in range(m):
          new_lock[x + i][y + j] += key[i][j]

 

그 후 자물쇠와 열쇠가 들어맞는지 검사하는 로직을 수행한다. 3배로 키운 new_lock 이므로 다시 3으로 나눠서 length를 구한다. 그리고 구한 length 값부터 length*2 값으로 이중 for문 돌면서(new_lock 의 가운데 부분만 순회) 모두 1인지 검사한다.

# 자물쇠의 중간 부분이 모두 1인지 확인
def check(new_lock):
    lock_length = len(new_lock) // 3
    for i in range(lock_length, lock_length * 2):
        for j in range(lock_length, lock_length * 2):
            if new_lock[i][j] != 1:
                return False
    return True

 

만약 False가 리턴되면 다음 작업을 위해 아까 new_lock 에 더했던 key값을 다시 빼준다.

# 자물쇠에서 열쇠를 다시 빼기
for i in range(m):
  for j in range(m):
    new_lock[x + i][y + j] -= key[i][j]

 

전체 코드

# 2차원 리스트 90도 회전하기
def rotate_a_matrix_by_90_degree(a):
    n = len(a) # 행 길이 계산
    m = len(a[0]) # 열 길이 계산
    result = [[0] * n for _ in range(m)] # 결과 리스트
    for i in range(n):
        for j in range(m):
            result[j][n - i - 1] = a[i][j]
    return result

# 자물쇠의 중간 부분이 모두 1인지 확인
def check(new_lock):
    lock_length = len(new_lock) // 3
    for i in range(lock_length, lock_length * 2):
        for j in range(lock_length, lock_length * 2):
            if new_lock[i][j] != 1:
                return False
    return True

def solution(key, lock):
    n = len(lock)
    m = len(key)
    # 자물쇠의 크기를 기존의 3배로 변환
    new_lock = [[0] * (n * 3) for _ in range(n * 3)]
    # 새로운 자물쇠의 중앙 부분에 기존의 자물쇠 넣기
    for i in range(n):
        for j in range(n):
            new_lock[i + n][j + n] = lock[i][j]

    # 4가지 방향에 대해서 확인
    for rotation in range(4):
        key = rotate_a_matrix_by_90_degree(key) # 열쇠 회전
        for x in range(n * 2):
            for y in range(n * 2):
                # 자물쇠에 열쇠를 끼워 넣기
                for i in range(m):
                    for j in range(m):
                        new_lock[x + i][y + j] += key[i][j]
                # 새로운 자물쇠에 열쇠가 정확히 들어 맞는지 검사
                if check(new_lock) == True:
                    return True
                # 자물쇠에서 열쇠를 다시 빼기
                for i in range(m):
                    for j in range(m):
                        new_lock[x + i][y + j] -= key[i][j]
    return False

 

 

출처: 이것이 코딩 테스트다 나동빈 저