Py) 프로그래머스 60059 자물쇠와 열쇠

https://programmers.co.kr/learn/courses/30/lessons/60059?language=python3 

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

1차: 30분

2차: 35분

0. 입출력

 

1. 김예고리즘

1-1. 내 로직

1) true의 조건에 대해 먼저 생각해봤다.

- lock의 0개수가 key의 1 개수보다 같거나 적어야한다.
- 전치 했을 때 하나라도 0이 겹치는게 있다면 상하좌우로 확인해주고..음..어..
    -> 이렇게 풀다가 lock은 중간에, key는 한쪽에 몰려있거나 하면 절대 안됨

그리고 뇌정지가 와서 한참 들여다보다가 그냥 검색함..

 

2. Solution

2-1. 사용 알고리즘: 완전탐색

2-2. 로직

1) 자물쇠를 가운데에 두고 자물쇠를 감싸는 새로운 행렬을 만든다.

새로운 행렬

2) 새로운 행렬을 키가 한칸씩 움직이며 탐색하는데, 이때 4번 회전하면서 전부 탐색한다.
   3<= M <= 20 이므로 원소를 모두 탐색할 경우 최대 20*20*4 = 1600 => 완전탐색으로 충분히 가능

2-3. 코드

def solution(key, lock):
    answer = False
    N = len(key)
    M = len(lock)

    newarray = [[0]*(M*3) for _ in range(M*3)]

    # 3배 확장된 new array(lock)를 만든다.
    for i in range(M):
        for j in range(M):
            newarray[i + M][j + M] = lock[i][j]

    for k in range(4):      # 4번 돌린다
        key = rotated(key)
        for a in range(1, M*2):         # 범위: 1 ~ M*2-1
            for b in range(1, M*2):

                for i in range(N):      # key의 인덱스
                    for j in range(N):
                        newarray[a+i][b+j] += key[i][j]

                if check(newarray) == True: # 맞음
                    return True
                else:
                    for i in range(N):
                        for j in range(N):
                            newarray[a+i][b+j] -= key[i][j]

    return answer


def rotated(key):
    rkey = [[0]*len(key) for _ in range(len(key))]
    for i in range(len(key)):
        for j in range(len(key)):
            rkey[j][len(key)-i-1] = key[i][j]
    return rkey


def check(arr):
    size = len(arr)//3     # 중간만 확인
    for i in range(size, size*2):
        for j in range(size, size*2):
            if arr[i][j] != 1: return False
    return True