[JAVA/PYTHON] 자물쇠와 열쇠(kakao 2020)

자물쇠와 열쇠 이미지

파이썬이 역시 간결하긴하다. 그래도 자바공부중이니 자바로 열심히 풀어봤다. 

문제를 접근하는 방법에 대해 고민을 많이 했다. 완전탐색으로 해도 될까했는데 대충 계산해본 결과 20*20 자물쇠와 20*20 키를 가지고 있다고 해도 시간초과는 나지 않을거 같았다. 

 

그래서 완전탐색으로 풀기로 한다.

 

풀기위해서 메소드를 나누는데,

 

1) 키를 90도씩 돌리는 함수를 작성하기로 한다. 이는 rotate라는 이름으로 작성하였다. 

2) 자물쇠 배열을 상하좌우 및 대각선까지 자물쇠 크기만큼 span한 새로운 자물쇠 배열을 초기화한다. 이를 spanLock이라는 이름으로 작성하였다.

3) 키와 자물쇠를 합쳤을 때 참인지 거짓인지 판별하는 check함수를 작성하였다.

4) span 되어있는 자물쇠에 키가 올수있는 모든 경우의 수를 탐색하는 for문을 작성한다.

 

위 4가지만 작성하면 된다.

 

아래는 파이썬과 자바의 코드다.

import copy

def Rotate(m,key):
    tmp = [[0 for _ in range(m)] for _ in range(m)]
    for i in range(m):
        for j in range(m):
            tmp[j][i]=key[m-1-i][j]
    return tmp

def check(t,m,_i,_j,key,span_lock):
    tmp = copy.deepcopy(span_lock)
    for i in range(_i,_i+m):
        for j in range(_j,_j+m):
            tmp[i][j]+=key[i-_i][j-_j]
            
    for i in range(t,t*2):
        for j in range(t,t*2):
            if tmp[i][j]!=1:
                return False
    return True

def solution(key,lock):
    n=len(lock)*3
    m=len(key)
    t=n//3
    st,ed=t-m+1,t*2
    span_lock = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(t,t*2):
        for j in range(t,t*2):
            span_lock[i][j]=lock[i-t][j-t]
        
    for _ in range(4):
        key = Rotate(m,key)
        for i in range(st,ed):
            for j in range(st,ed):
                if check(t,m,i,j,key,span_lock):
                    return True
    else:
        return False

class Solution {
    public int[][] SpanningLock(int[][] lock){
        int n = lock.length;
        int[][] spanLock = new int[n*3][n*3];

        for(int i=n;i<2*n;i++){
            for(int j=n;j<2*n;j++){
                spanLock[i][j]=lock[i-n][j-n];
            }
        }
        return spanLock;
    }

    public boolean check(int s1,int s2,int[][] key,int[][] spanLock){
        int n = spanLock.length;
        int tmp[][] = new int[n][n];

        for(int i=n/3;i<(n/3)*2;i++){
            for(int j=n/3;j<(n/3)*2;j++){
                tmp[i][j]=spanLock[i][j];
            }
        }

        for(int i=s1;i<s1+key.length;i++){
            for(int j=s2;j<s2+key.length;j++){
                tmp[i][j] = key[i-s1][j-s2] + spanLock[i][j];
            }
        }

        for(int i=n/3;i<(n/3)*2;i++){
            for(int j=n/3;j<(n/3)*2;j++){
                if (tmp[i][j]!=1){
                    return false;
                }
            }
        }

        return true;
    }

    public int[][] rotate(int[][] key){
        int m = key.length;
        int[][] ret = new int[m][m];
        for(int i=0;i<m;i++){   
            for(int j=0;j<m;j++){
                ret[i][j] = key[m-j-1][i];
            }
        }
        return ret;
    }


    public boolean solution(int[][] key, int[][] lock) {
        int m = key.length;
        int n = lock.length;
        int[][] spanLock = SpanningLock(lock);


        for(int r=0;r<4;r++){
            key = rotate(key);
            for(int i=n-m+1;i<2*n;i++){
                for(int j=n-m+1;j<2*n;j++){
                    if(check(i,j,key,spanLock)){
                        return true;
                    }
                }
            }
        }

        return false;
    }
}