👀 문제
https://programmers.co.kr/learn/courses/30/lessons/60059
👊 도전
1. 설계
- 모든 경우를 다 확인해야한다.
- 열쇠를 90도 회전하는 rotate()를 구현한다.
- 키가 자물쇠의 (0,0)부터 겹치는 경우~(lock.length-1, lock.length-1)만 겹치는 경우를 모두 확인하면 된다.
- 패딩을 두어 중간에 회전한 키를 두고, 자물쇠와 겹치게 하여 키와 자물쇠가 맞는지 확인한다.
2. 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
*
* @author HEESOO
*
*/
class Solution {
public boolean solution(int[][] key, int[][] lock) {
int size=lock.length-1;
for(int i=0;i<4;i++) {
key=rotate90(key);
key=padding(key, size);
for(int kr=0;kr<key.length-size;kr++) {
for(int kc=0;kc<key[0].length-size;kc++) {
boolean flag=true;
for(int lr=0;lr<lock.length;lr++) {
for(int lc=0;lc<lock[0].length;lc++) {
if(lock[lr][lc]==key[kr+lr][kc+lc]) flag=false;
if(!flag) break;
}
if(!flag) break;
}
if(flag) return true;
}
}
}
return false;
}
public int[][] rotate90(int[][] key){
int[][] result=new int[key.length][key[0].length];
for(int i=0;i<key.length;i++) {
for(int j=0;j<key[i].length;j++) {
result[i][j]=key[key[i].length-j-1][i];
}
}
return result;
}
public int[][] padding(int[][] key, int size){
int[][] result=new int[key.length+size*2][key[0].length+size*2];
for(int i=0;i<key.length;i++) {
for(int j=0;j<key[i].length;j++) {
result[i+size][j+size]=key[i][j];
}
}
return result;
}
}
3. 결과
🤟 성공 🤟
4. 설명
- key를 90도 회전한다
- 90도 회전하는 함수 rotate90()을 구현한다.
- 위 함수를 4번 부르면 90, 180, 270, 0도 회전하는 키를 모두 확인할 수 있다.
- 3x3행렬 키를 90도 회전하면, 원래 키의 원소 (0,0)를 90도 회전시키면 (2,0)으로 이동하고, (0,1)->(1,0), (0,2)->(0,0)이다.
- 따라서 key가 nxm행렬이라 할 때, result[i][j]=key[m-j-1][i]가 된다.
- padding을 만들어 키가 자물쇠에 겹치는 범위를 만든다
- 열쇠는 자물쇠에 모두 겹치지 않아도 되므로, 열쇠가 자물쇠의 (0,0)부터 끝까지 겹치는 경우부터 마지막 원소만 겹치는 경우까지를 확인하면 된다.
- 이를 위해 패딩을 준다.
- 패딩의 크기는
key크기+(자물쇠크기-1)*2이다. 일단 정중앙에 키를 둬야하므로 key크기가 필요하고, 열쇠가 자물쇠의 맨 끝만 탐색하는 경우와 맞물리는 경우를 위해 (자물쇠크기-1)*2가 필요하다. - 생성된 패딩의 중앙에 키를 넣어서 리턴한다.
- 자물쇠가 풀리면 true를 리턴한다
- 90도 회전한 키를 가지고 패딩의 중앙에 넣은 후 리턴받아 key에 저장한다.
- kr, kc는 키의 가로, 세로 인덱스이고, lr, lc는 자물쇠의 가로, 세로 인덱스이다.
- kr, kc의 범위는 -size하여 패딩된 key의 길이에서 원래 key의 길이만큼만 확인하게 해준다.
- flag를 두어 lock과 일치한다면 풀 수 없는 경우이므로 false로 바꾼 후 break를 통해 시간을 단축한다.
- flag가 변하지 않는 경우, 즉 자물쇠를 풀 수 있는 경우에만 true를 리턴한다.