자물쇠와 열쇠 : https://programmers.co.kr/learn/courses/30/lessons/60059
Problems
Solves
[1]첫번째 스스로 풀었을때는 Key에서 돌기의 좌표 리스트 keyPiontList와 Lock의 홈의 좌표 리스트 lockHoleList를 만들어 재귀 함수 matching함수를 만들어 구현했다.
matching함수는 재귀 함수로 key를 90도씩 회전시키면서 회전된 keyPointList좌표를 갱신해주고 상하좌우로 이동시킨 keyPointList좌표를 갱신해주어서 이동한 방향으로 이동 횟수를 카운트하여 구현하였다.
테스트케이스는 통과했었지만 당연히 시간초과로 다시 구현해야했다.
[2]진짜 key의 배열을 확장시킬 생각은 어떻게 하는지 감탄할수밖에 없었다.
key배열을 90도씩 회전시키고 padding함수를 이용해 key배열에서 x축, y축을 각각 paddingSize(자물쇠 크기 -1)만큼 확장시켜주었다.
그리고 확장된 key인 paddingKey에서 시작 좌표를 지정해서 시작 좌표부터 자물쇠 크기까지 서로를 비교하는 matching함수에서 각 좌표의 합(paddingKey[i][j]+lock[k][k])이 1이 아니라면 자물쇠의 홈에 키의 돌기가 맞물리지 않는 것이기 때문에 바로 false를 반환해주고 반복문을 통과한다면 true를 반환해준다.
matching함수가 true를 반환하면 해당 키로 자물쇠를 열수있는것이기 때문에 true를 반환해준다.
그림으로 알아보자
예제 코드를 기준으로 설명해보자면, key와 lock의 초깃값이다.
위의 설명대로 보면 key를 90도 회전시키고 paddingSize만큼 key를 확장시킨 paddingKey를 생성해준다. 그리고 paddingKey에서 시작 좌표를 지정해서 자물쇠 크기만큼 비교를 해준다.
위의 그림을 설명하면 빨간 부분이 기존 key에서 paddingSize만큼 확장된 부분(확장된 배열중 lock의 크기까지만 표시, 아래 빨간 부분은 그냥 표시해둔겁니다.), paddingKey에서 가져온 시작좌표(startX, startY)가 (0,0)이라고 할때의 상황이다.
paddingKey에서 (0,0)부터 시작해서 자물쇠의 크기까지인 (2,2)까지 paddingKey와 lock을 비교한다.
이 때 lock의 홈 부분(0)에는 paddingKey에 1(돌기)이 아닌 0(홈)이기 때문에 (paddingKey[1][3]+lock[1][3] == 0)false를 반환해준다.
반복으로 수행하다보면 paddingKey에서 가져온 시작 좌표가 (2,2)일 때 lock크기만큼 비교하면 paddingKey[2][3]+lock[1][2] == 1, paddingKey[3][2]+lock[2][1] == 1이기 때문에 모든 좌표간의 합이 1이 되어 matching함수에서 true를 반환할수 있게 된다.
Code
import java.util.List;
import java.util.ArrayList;
class Solution {
int M;
int N;
int paddingSize;
public boolean solution(int[][] key, int[][] lock) {
M = key.length;
N = lock.length;
//key의 각 축을 확장시킬 크기
paddingSize = N-1;
for(int i=0;i<4;i++){
//i마다 90도씩 회전
key = turnKey(key);
//key배열 확장
int[][] paddingKey = padding(key);
//시작 좌표에서 lock의 크기 만큼 비교해야하므로
//최대 paddingKey.length에서 paddingSize(lock.length-1)을 뺀곳까지만 비교할수 있다.
for(int ky=0;ky<paddingKey.length-paddingSize;ky++){
for(int kx=0;kx<paddingKey[ky].length-paddingSize;kx++){
if(matching(paddingKey,lock,ky,kx)){
return true;
}
}
}
}
return false;
}
boolean matching(int[][] key, int[][] lock, int startY, int startX){
for(int i=0;i<N*N;i++){
int ly = i/N;
int lx = i%N;
//각 좌표의 합이 1이 아니라면 돌기와 홈이 맞물리지 않은 곳이기 때문에 false반환
if(lock[ly][lx]+key[startY+ly][startX+lx] != 1) return false;
}
return true;
}
//함수 호출때마다 90도 회전한 배열 생성
int[][] turnKey(int[][] key){
int[][] turn = new int[M][M];
for(int i=0;i<M*M;i++){
if(key[i/M][i%M]==1){
int y = i/M;
int x = i%M;
turn[x][(M-1)-y]=1;
}
}
return turn;
}
//paddingSize만큼 각 좌표를 확장시켜서 반환
int[][] padding(int[][] key){
int[][] paddingKey = new int[M+2*paddingSize][M+2*paddingSize];
for(int i=0;i<M*M;i++){
if(key[i/M][i%M]==1){
paddingKey[(i/M)+paddingSize][(i%M)+paddingSize] = 1;
}
}
return paddingKey;
}
class Point{
int x;
int y;
public Point(int x, int y){
this.x = x;
this.y = y;
}
}
}Result
