[프로그래머스] 자물쇠와 열쇠

로직은 이렇게 구성했습니다.

만약 이렇게 key의 크기가 3*3이고 lock의 사이즈가 4일때

(빨간 곳은 겹치는 배열) 이러한 배열을 만드시는 분들이 많더라구요.

그런데 어차피 탐색을 할 때 기준점을 키의 왼쪽 위 즉

이렇게 잡는다면 만든 큰 배열에서 기준점이 들어갈 수 있는 곳은 배열의 크기보다 꽤나 작습니다.

연두색 부분은 검사를 할 필요도 없는 부분입니다. 기준점이 연두색 부분에 있으면 모든 값이 자물쇠 바깥의 값들이니까요. 이렇게 한다면 배열의 크기를 (자물쇠의 크기+(열쇠의 크기-1)*2)^2 에서 (자물쇠의 크기+열쇠의 크기-1)^2로 줄일 수 있습니다. 짠돌이 호석의 경우 무조건 정사각형도 아니고 크기도 어떤것이 크다! 라고 하기 애매한 것들도 많아서 구현에 실패했었지만 이 문제는 가능할 것 같아서 이렇게 짜주었습니다.

결론적으로 저 노란 부분의 배열만큼의 배열을 만들어주었습니다.

해당 크기의 배열을 만들 빨간색 부분에는 lock의 값들이 위치하게 해주었습니다. 그리고 마찬가지로 탐색을 진행할 때 노란 부분의 위치는 탐색을 진행할 필요가 없습니다. 마찬가지로 저 부분은 자물쇠의 밖이니까요!

	for i in range(mx_len):
            for j in range(mx_len):
                correct=0
                unable=False
                for ii in range(l1):
                    nowy=i+ii
                    if l1-2<nowy<mx_len:
                        for jj in range(l1):
                            nowx=j+jj
                            if l1-2<nowx<mx_len:
                                if rotated_key[ii][jj]==1 and bigmap[nowy][nowx]==0:
                                    correct+=1
                                elif rotated_key[ii][jj]&bigmap[nowy][nowx]==1:
                                    unable=True
                                    break
                    if unable:
                        break
                if unable:
                    continue
                if correct==lock_hole:
                    return True

맞은 것을 표현할 변수 correct와 조건에 맞지 않으면 다중 반복문을 탈출할 때 필요한 unable을 선언해준뒤 탐색을 진행하였습니다.

탐색 방법은 다음과 같습니다.

해당 길이 범위 내의 좌표를 정한 뒤 key의 값만큼 오른쪽 아래 방향으로 탐색해주었습니다

파란색 위치를 기준으로 골랐을 때

하늘색 부분을 탐색

이때 탐색하는 부분이 빨간색 배열의 바깥이 아닐때만 비교해주었습니다.

 

아래는 코드 입니다.

def make_big_table(arr1,arr2): # 큰 배열을 만드는 함수
    l1=len(arr1)-1
    l2=len(arr2)
    n_arr=[[0 for i in range(l1+l2)] for i in range(l1)] # 큰 배열의 윗 부분을 미리 만들어놓기
    for i in range(l2):
        n_arr.append([0 for i in range(l1)]+arr2[i]) # key의 크기-1 만큼 [0,0,0...]+ lock의 한 줄

    return n_arr,len(n_arr) # 만든 큰 배열과 큰 배열의 한 변의 길이를 리턴

def rotate(arr1): # 회전시킨 4개의 모양을 리턴해주느 함수
    l1=len(arr1)
    rotated=[arr1,[],[],[]]
    for _ in range(3):
        at_rotated=[[0 for i in range(l1)]for i in range(l1)]
        for i in range(l1):
            for j in range(l1):
                at_rotated[~j][i]=rotated[_][i][j]
        rotated[_+1]=at_rotated
    return rotated

def solution(key,lock):
    l1=len(key)
    l2=len(lock)
    bigmap,mx_len=make_big_table(key,lock) # 큰 배열과 최대 길이 저장
    rotated_keys=rotate(key) # 회전한 4개의 모습 저장
    lock_hole=0 # 자물쇠의 구멍 개수
    
    # 2중 for문으로 자물쇠의 구멍 개수를 구해줌
    for i in range(l2):
        for j in range(l2):
            if lock[i][j]==0: 
                lock_hole+=1
    
    for rotated_key in rotated_keys: # 가장 바깥에 회전한 열쇠들
        for i in range(mx_len): # 큰 배열내의 y
            for j in range(mx_len): # 큰 배열내의 x
                correct=0 # 채운 구멍의 갯수
                unable=False # 2중 for문을 탈출하고 구멍 갯수 비교를 스킵시켜줄 변수
                for ii in range(l1): # key값만큼 탐색
                    nowy=i+ii
                    if l1-2<nowy<mx_len: # lock의 범위 내에 속한다면
                        for jj in range(l1):
                            nowx=j+jj
                            if l1-2<nowx<mx_len: # lock의 범위 내에 속한다면
                                if rotated_key[ii][jj]==1 and bigmap[nowy][nowx]==0: # 만약 key에서 저 좌표의 값이 0이고, 큰 배열의 좌표의 값은 0이라면 
                                    correct+=1 # 하나 채워준다.
                                elif rotated_key[ii][jj]&bigmap[nowy][nowx]==1: # 만약 &연산 결과가 1이라면 (둘다 1이라면)
                                    unable=True # 어떻게 해도 불가능이다
                                    break
                    if unable:
                        break
                if unable:
                    continue
                if correct==lock_hole: #만약 구멍의 개수와 채운 개수가 같다면
                    return True
    return False