⭐ 문제 링크
1. 접근법
구현 문제이다.
해당 문제의 해결법은 브루트 포스로 그냥 모든 조합을 다 검사해보는 것 입니다.
그렇기 위해서 아래와 같은 이차원 배열을 생성합니다.
해당 이차원 배열은 키와 자물쇠가 겹칠 수 있는 최대 범위를 지정해주는 판이라고 보면 됩니다.
그 후 해당 키를 차례대로 90도 방향 씩 회전해서, 자물쇠의 모든 원소가 모두 1이 되는지 확인할 것 입니다.
(만약 0이 된다면 자물쇠의 홈에 키가 맞지 않다는 의미이다.)
(만약 2가 된다면 열쇠의 돌기와 자물쇠의 돌기가 맞물렸다는 의미이다.)
즉 풀이는 아래와 같습니다.
- "자물쇠의 길이 + (키의길이*2) - 2" 크기의 배열 map[][]을 만든다.
- map에 lock 배열의 값을 위치에 맞게 입력한다.
- 키가 자물쇠에 맞는지 체크한다.
- 키가 안 맞다면 시계 방향으로 90도 회전시키고 확인한다. (총 4번 반복)
2. 코드
import java.util.*;
class Solution {
public boolean solution(int[][] key, int[][] lock) {
boolean answer = true;
int m = key.length;
int n = lock.length;
int len = n+m*2-2;
int[][] map = new int[len][len]; // 확장시킨 배열
/* 확장시킨 배열에 Lock 표시 */
for(int i=m-1; i<m+n-1 ; i++){
for(int j=m-1; j<m+n-1; j++){
map[i][j] = lock[i-(m-1)][j-(m-1)];
}
}
/* 현재 인덱스에서 시계방향으로 4번 조사 */
for(int i=0; i<4; i++){
if(check(map, key, n)){
return true;
}
rotate(key); // 시계방향 90도 회전
}
return false;
}
/* 키가 자물쇠에 맞는지 체크 */
public static boolean check(int[][] map, int[][] key, int lockLen){
int keyLen = key.length;
int mapLen = map.length;
for(int i=0; i<mapLen-keyLen+1; i++){
for(int j=0; j<mapLen-keyLen+1; j++){
/* map에 key를 더함 */
for(int k=0; k<keyLen; k++){
for(int l=0; l<keyLen; l++){
map[i+k][j+l] += key[k][l];
}
}
/* 자물쇠 부분이 전부 1이 됐는지 확인 */
boolean flag = true;
for(int k=keyLen-1; k<keyLen+lockLen-1; k++){
for(int l=keyLen-1; l<keyLen+lockLen-1; l++){
if(map[k][l] != 1){ // 1이 아니면 홈이 안 맞는 것임
flag = false;
break;
}
}
if(!flag) break;
}
if(flag) return true; // 전부 1이였다면 true
/* map을 원상 복귀 시킴 -> map에서 key를 뺌 */
for(int k=0; k<keyLen; k++){
for(int l=0; l<keyLen; l++){
map[i+k][j+l] -= key[k][l];
}
}
}
}
return false;
}
/* key 시계 방향 90도 회전 */
public static void rotate(int[][] key){
int len = key.length;
int[][] temp = new int[len][len];
for(int i=0; i<len; i++){
for(int j=0; j<len; j++){
temp[i][j] = key[len-j-1][i];
}
}
for(int i=0; i<len; i++){
for(int j=0; j<len; j++){
key[i][j] = temp[i][j];
}
}
}
}이제 해당 코드를 하나하나 설명을 해보겠습니다.
2-1. main
class Solution {
public boolean solution(int[][] key, int[][] lock) {
boolean answer = true;
int m = key.length;
int n = lock.length;
int len = n+m*2-2;
int[][] map = new int[len][len]; // 확장시킨 배열
/* 확장시킨 배열에 Lock 표시 */
for(int i=m-1; i<m+n-1 ; i++){
for(int j=m-1; j<m+n-1; j++){
map[i][j] = lock[i-(m-1)][j-(m-1)];
}
}
/* 4번(90도 회전 경우의 수) 조사 */
for(int i=0; i<4; i++){
if(check(map, key, n)){
return true;
}
rotate(key); // 시계방향 90도 회전
}
return false;
}해당 코드에서 4번 조사한다는 의미는 첫 번째 방향으로 해당 map 배열을 처음부터 끝까지 조사했을 때, 정답을 찾지 못한다면 키의 방향을 시계방향으로 90도 회전한 후 다시 처음부터 끝까지 for문을 동작시킨다는 의미입니다.
2-3. check(map, key, n)
해당 함수는 키가 자물쇠에 맞는지 체크해주는 함수입니다.
기본 로직은 각 키와 자물쇠는 돌기 부분은 1입니다.
그 후 이중 for문을 돌며 현재 겹쳐지는 부분의 각 키와 자물쇠의 값을 더합니다.
-
만약 더해진 값이 2라면, 해당 자물쇠와 키의 돌기부분이 겹쳐졌다는 의미입니다.
-
만약 더해진 값이 1로 유지된다면, 자물쇠의 홈 부분과 열쇠의 돌기부분이 잘 맞물렸다는 의미 입니다.
해당 로직에서는 모든 자물쇠와 열쇠의 겹쳐지는 부분을 더했을 때, 최종 map의 모든 원소가 1인, 즉 자물쇠의 홈 부분과 열쇠의 돌기 부분이 정확히 맞아 떨어지는 경우를 찾는 함수입니다.
< 변수 설명 >
: 해당 코드에서 설명하는 변수들에 대해 설명하겠습니다.
< i, j >
- 확장된 map 배열에서 키를 올려놓는 시작 위치의 행과 열을 나타냅니다.
- 키를 map 배열 위에 올려놓는 모든 가능한 위치를 검사하기 위해 사용됩니다.
- map 배열 내에서 자물쇠가 위치한 범위는 keyLen + lockLen - 1이므로, i와 j의 범위는 0 ~ mapLen-keyLen+1입니다.
-> map 배열 내에서 자물쇠의 범위를 넘어가면 검사할 필요가 없기 때문
< k, l >
- 키 배열 key의 행과 열을 나타냅니다.
- 키 배열의 각 원소를 map 배열에 더하거나 빼는 작업을 수행할 때 사용됩니다.
- 키 배열의 크기는 keyLen이므로, k와 l의 범위는 0 ~ keyLen-1입니다.
즉, i, j는 키를 map 배열에 올려놓는 시작 위치를, k, l은 키 배열 내부의 원소 위치를 나타내는 변수입니다. 이를 통해 키를 map 배열 위에 올려놓고, 자물쇠 부분이 모두 1인지 확인하는 작업을 수행합니다.
/* 키가 자물쇠에 맞는지 체크 */
public static boolean check(int[][] map, int[][] key, int lockLen){
int keyLen = key.length;
int mapLen = map.length;
//
for(int i=0; i<mapLen-keyLen+1; i++){
for(int j=0; j<mapLen-keyLen+1; j++){
/* map에 key를 더함 */
for(int k=0; k<keyLen; k++){
for(int l=0; l<keyLen; l++){
map[i+k][j+l] += key[k][l];
}
}
/* 자물쇠 부분이 전부 1이 됐는지 확인 */
boolean flag = true;
for(int k=keyLen-1; k<keyLen+lockLen-1; k++){
for(int l=keyLen-1; l<keyLen+lockLen-1; l++){
if(map[k][l] != 1){ // 1이 아니면 홈이 안 맞는 것임
flag = false;
break;
}
}
if(!flag) break;
}
if(flag) return true; // 전부 1이였다면 true
/* map을 원상 복귀 시킴 -> map에서 key를 뺌 */
for(int k=0; k<keyLen; k++){
for(int l=0; l<keyLen; l++){
map[i+k][j+l] -= key[k][l];
}
}
}
}
return false;
}예를 들어, 만약 key와 lock이 다음과 같았다고 가정한 후, map에 key를 더하는 함수를 진행시켜 주면, 결과는 아래와 같습니다.
이런 방식으로 처음부터 끝까지 모두 더해준 후, boolean flag = true;를 이용하여 map 배열 내의 자물쇠의 모든 원소가 1인지 확인합니다. 만약 1이 아니라면 map 배열은 다음 계산에서 이용되어야 하므로 원상복구를 시켜줍니다.
(원상복구 시켜주는 로직은 key를 더하는 로직과 동일합니다.)
2-3. rotate(int[][] key)
해당 함수는 key를 시계방향 대로 90도 회전시켜주는 함수입니다.
90도 바꾼 key의 행과 열은 다음과 같습니다.
temp[i][j] = key[len-j-1][i];
/* key 시계 방향 90도 회전 */
public static void rotate(int[][] key){
int len = key.length;
int[][] temp = new int[len][len];
for(int i=0; i<len; i++){
for(int j=0; j<len; j++){
temp[i][j] = key[len-j-1][i];
}
}
for(int i=0; i<len; i++){
for(int j=0; j<len; j++){
key[i][j] = temp[i][j];
}
}
}
예시를 가져와보았습니다.
key는 문제에서 주어진 배열이고, temp는 현재 해당 key를 시계방향으로 90도 돌린 상태입니다.
위 식을 이용하면 아래와 같이 90도 돌려진 key의 값을 얻을 수 있습니다.
결과
