이번에 풀어본 문제는
프로그래머스 자물쇠와 열쇠 입니다.

📕 문제 링크

❗️코드

import java.util.*;
class Solution {
    static int n,cnt,keyLen;
    static int [][] map;
    public boolean solution(int[][] key, int[][] lock) {
        boolean answer = false;
        keyLen = key.length;
        n = 2*(key.length-1);
        cnt = 0;
        int mapLen = lock.length + n;
        map = new int[mapLen][mapLen];
        for(int i = 0; i < lock.length; ++i)
        {
            for(int j = 0; j < lock.length; ++j)
            {
                if(lock[i][j] == 1) map[i+key.length-1][j+key.length-1] = 1;
                else cnt++;
            }
        }

        int [][] tmpKey = new int[key.length][key.length];
        for(int i = 0; i < key.length; ++i)
        {
            System.arraycopy(key[i],0,tmpKey[i],0,key[i].length);
        }
        for(int t = 0; t < 4; ++t)
        {
            if(unlock(tmpKey))
            {
                answer = true;
                break;
            }
            tmpKey = rotate(tmpKey);
        }
        return answer;
    }
    static boolean unlock(int [][] key)
    {
        int correct;
        for(int i = 0; i <= map.length-keyLen; ++i)
        {
            for(int j = 0; j <= map.length-keyLen; ++j)
            {
                correct = 0;
                next : for(int k = i; k < i+keyLen; ++k)
                {
                    for(int l = j; l < j+keyLen; ++l)
                    {
                        if(inArr(k,l))
                        {
                            if(map[k][l] == 0)
                            {
                                if(key[k-i][l-j] == 1) correct++;
                            }
                            else
                            {
                                if(key[k-i][l-j] == 1) continue next;
                            }
                        }
                    }
                    if(correct == cnt) return true;
                }
            }
        }
        return false;
    }
    static int [][] rotate(int [][] key)
    {
        int len = key.length;
        int [][] arr = new int[len][len];

        for(int i = 0; i < len; ++i)
        {
            for(int j = 0; j < len; ++j)
            {
                arr[i][j] = key[len-j-1][i];
            }
        }
        return arr;
    }
    static boolean inArr(int i, int j)
    {
        return i >= keyLen-1 && i <= map.length-keyLen && j >= keyLen-1 && j <= map.length-keyLen;
    }
}

📝 풀이

주어진 lock배열을 확장시켜 key와 비교할 수 있는 모든 경우의수를 조사했습니다.
기존 lock배열의 범위밖은 조사할 필요가 없으므로, inArr()함수로 넘겨줍니다.
만약 lock이 빈칸일 때 key의값이 1이라면 카운트를 올려주고, 돌기(1) 끼리 겹치게 되면 바로 다음 반복으로 넘어가줍니다.
탐색을 마치고 해당 배치로의 카운트 수와 lock 배열의 홈의 총 개수가 일치한다면 true를 리턴해줍니다.

📜 후기

하루 알고리즘 공부시간을 몽땅 갈아넣은 문제입니다.. 역시 레벨3은 쉽지않네요 ㅠㅠ
예제만 보고 key와 lock 배열의 크기가 같게 주어지는 줄 알고 풀어서, 맞는데 도대체 왜 틀리는건지 고민만 3~4시간은 한거같아요 ㅋㅋㅋㅋㅋ 어이가없었습니다..
캐릭터가 너무 귀여워서 그림만 구경했나봐요 ㅡ ㅡ^
앞으로는 주어진 조건을 꼼꼼히 읽어봐야겠습니다!!