[프로그래머스] 파이썬 _ 자물쇠와 열쇠 (2020 KAKAO BLIND)

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

코딩테스트 연습 - 자물쇠와 열쇠

 

문제유형 : 2차원배열, 구현

 

문제풀이 :

 

• 이 문제의 핵심은 기존 lock배열을 expand해서 확장된 배열을 만드는 것이다.
  • 확장된 배열의 정중앙에 기존 lock이 위치한다.
  • 확장된 배열 위에서 key를 이동시키는것이다.
  • 얼만큼 확장시키나? new_n = (3*n)-2 만큼 확장시킨다 (key는 항상 lock크기 이하인데, key가 가장 클때, 즉 lock의 크기와 같을때 좌측상단에 key를 위치시켰을때 우측하단 꼭지점한개가 겹치는크기)

 

• key의 이동
  • 확장된 배열 위를 움직이면서, 중앙의 lock배열의 값을 체크하면서 홈이 모두 사라졌는지 확인한다.
  • 모두 이동했는데 아직 자물쇠가 풀리지않았다면 시계방향으로 90도씩 회전한다.
    • 회전은 총 3번 진행하고 총 4개의 key 배열을 확인하게된다. (기존 + 회전한 3번)
  • key가 배열위에서 얼만큼 움직일수 있는가?
    • 좌측 상단 꼭지점의 위치를 x,y라고하면 이 x,y가 최대 new_n - m 까지 이동할수 있다. ( 벗어나면 key가 확장된 배열에서마저도 삐져나가게됨 - 인덱스에러)

 

• 2차원 배열의 회전 - clock_rotate함수
  • 2차원 배열의 회전시 규칙이 있다.
  • 회전후 행 = 회전 전 열
  • 회전후 열 = 배열크기-1-회전전 행

  •     new_key = [[0] * m for _ in range(m)]
    
        # 시계방향으로 회전
        for i in range(m):
            for j in range(m):
                new_key[j][m-1-i] = key[i][j]

• 이 방법 말고 zip함수를 이용한 방법도 있었다.

• def rotate90(arr):
      return list(zip(*arr[::-1]))

 

정답코드 :

rotate_list = []

def clock_rotation(key, depth):

    if depth == 3:
        return

    m = len(key)

    new_key = [[0] * m for _ in range(m)]

    # 시계방향으로 회전
    for i in range(m):
        for j in range(m):
            new_key[j][m-1-i] = key[i][j]

    rotate_list.append(new_key)
    return clock_rotation(new_key, depth+1)


def solution(key, lock):

    # 회전한 키들을 담는 리스트 rotation_list
    rotate_list.append(key)
    clock_rotation(key, 0)

    m = len(key)
    n = len(lock)
    new_n = (3*n)-2

    # 크기를 키운 새로운 lock배열
    new_lock = [[0] * new_n for _ in range(new_n)]

    # new_lock의 중앙에 기존 lock배열을 위치시킨다.
    for i in range(n):
        for j in range(n):
            new_lock[i+n-1][j+n-1] = lock[i][j]

    # 회전한 키에 대해서
    for round in rotate_list:
        for i in range(new_n-m):
            for j in range(new_n-m):
                attach_key(i,j,m,round,new_lock)
                if check(new_lock, n):
                    return True
                dettach_key(i,j,m,round,new_lock)
    return False


# 좌측상단 꼭지점이 x,y일때 키를 붙이는 함수
def attach_key(x,y, m, key, new_lock):
    for i in range(m):
        for j in range(m):
            new_lock[x+i][y+j] += key[i][j]

def dettach_key(x,y,m,key,new_lock):
    for i in range(m):
        for j in range(m):
            new_lock[x+i][y+j] -= key[i][j]

# 자물쇠가 풀렸나?
def check(new_lock, n):
    middle = get_middle(new_lock, n)
    for line in middle:
        for i in line:
            if i != 1: # 홈이 남아있다.
                return False
    return True

def get_middle(new_lock, n):
    middle = [[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            middle[i][j] = new_lock[i+n-1][j+n-1]
    return middle