[프로그래머스] 자물쇠와 열쇠(2020 KAKAO BLIND RECRUITMENT)

 

 

자물쇠와 열쇠 문제를 풀어보았습니다.

 

 

0과 1(홈과 돌기)로 이루어진 2차원 배열 key와 lock이 주어졌을 때, key가 lock의 홈과 돌기에 꼭 맞는 경우 자물쇠를 열 수 있다고 판단합니다.

key는 90도 회전이 가능하고, 상하좌우로 이동할 수 있습니다.

 

key의 크기인 M과 lock의 크기인 N이 20 이하로 제한되어있기 때문에, key가 위치할 수 있는 모든 경우의 수를 반복해서 체크했습니다.

 

 

applyLock이라는 새로운 2차원 배열을 선언했습니다. 크기는 열쇠가 자물쇠의 양 끝에 한 칸씩 걸릴 수 있는 자물쇠 길이 + 2 * (열쇠 길이 - 1)로 생성했습니다. applyLock배열의 정중앙에 lock배열 데이터를 넣습니다.

int keyLen = key.length;
int lockLen = lock.length;
int[][] turnedKey = key;
int[][] applyLock = new int[lockLen+2*keyLen-2][lockLen+2*keyLen-2];

for(int i=keyLen-1; i<keyLen-1+lockLen; i++){
    for(int j=keyLen-1; j<keyLen-1+lockLen; j++){
        applyLock[i][j] = lock[i-keyLen+1][j-keyLen+1];
    }
}

그 위로 key배열을 순회하면서 자물쇠가 열리는지 확인합니다.

for(int a=0; a<4; a++){           
     for(int i=0; i<=applyLock.length-keyLen; i++){
         for(int j=0; j<=applyLock.length-keyLen; j++){
             if(checkLockOpen(turnedKey, applyLock, i, j, keyLen, lockLen)) return true;
         }
     }
     turnedKey = turnKey(turnedKey);
 }
 
 public boolean checkLockOpen(int[][] turnedKey, int[][] applyLock, int x, int y, int keyLen, int lockLen){
        
        for(int i=keyLen-1; i<keyLen-1+lockLen; i++){
            for(int j=keyLen-1; j<keyLen-1+lockLen; j++){
                boolean flag = false;
                if(i>=x && i<x+keyLen && j>=y && j<y+keyLen){
                    if(applyLock[i][j]==1 && turnedKey[i-x][j-y]==1) return false;
                    if(applyLock[i][j]==0 && turnedKey[i-x][j-y]==0) return false;
                    if(applyLock[i][j]==0 && turnedKey[i-x][j-y]==1) flag = true;
                }
                if(applyLock[i][j]==0 && !flag) return false;
            }
        }
        return true;
    }

applyLock 배열을 한 번 돌면서 확인한 후에 자물쇠가 열리지 않으면 key를 90도 회전합니다.

public int[][] turnKey(int[][] turnedKey){
        int turnedKeyLen = turnedKey.length;
        int[][] tempKey = new int[turnedKeyLen][turnedKeyLen];
        for(int i=0; i<turnedKeyLen; i++){
            for(int j=0; j<turnedKeyLen; j++){
                tempKey[i][j] = turnedKey[j][turnedKeyLen-i-1];
            }
        }
        return tempKey;
    }

 

 

전체 코드

class Solution {
    public boolean solution(int[][] key, int[][] lock) {
        boolean answer = true;
        int keyLen = key.length;
        int lockLen = lock.length;
        int[][] turnedKey = key;
        int[][] applyLock = new int[lockLen+2*keyLen-2][lockLen+2*keyLen-2];
        for(int i=keyLen-1; i<keyLen-1+lockLen; i++){
            for(int j=keyLen-1; j<keyLen-1+lockLen; j++){
                applyLock[i][j] = lock[i-keyLen+1][j-keyLen+1];
            }
        }
        for(int a=0; a<4; a++){           
            for(int i=0; i<=applyLock.length-keyLen; i++){
                for(int j=0; j<=applyLock.length-keyLen; j++){
                    if(checkLockOpen(turnedKey, applyLock, i, j, keyLen, lockLen)) return true;
                }
            }
            turnedKey = turnKey(turnedKey);
        }
        return false;
    }
    public int[][] turnKey(int[][] turnedKey){
        int turnedKeyLen = turnedKey.length;
        int[][] tempKey = new int[turnedKeyLen][turnedKeyLen];
        for(int i=0; i<turnedKeyLen; i++){
            for(int j=0; j<turnedKeyLen; j++){
                tempKey[i][j] = turnedKey[j][turnedKeyLen-i-1];
            }
        }
        return tempKey;
    }
    public boolean checkLockOpen(int[][] turnedKey, int[][] applyLock, int x, int y, int keyLen, int lockLen){
        
        for(int i=keyLen-1; i<keyLen-1+lockLen; i++){
            for(int j=keyLen-1; j<keyLen-1+lockLen; j++){
                boolean flag = false;
                if(i>=x && i<x+keyLen && j>=y && j<y+keyLen){
                    if(applyLock[i][j]==1 && turnedKey[i-x][j-y]==1) return false;
                    if(applyLock[i][j]==0 && turnedKey[i-x][j-y]==0) return false;
                    if(applyLock[i][j]==0 && turnedKey[i-x][j-y]==1) flag = true;
                }
                if(applyLock[i][j]==0 && !flag) return false;
            }
        }
        return true;
    }
}