[프로그래머스] 60059 자물쇠와 열쇠 (JAVA) - 풀이

문제 분석

• 자물쇠 영역을 벗어나면
  • 자물쇠를 여는데 영향을 주지 않는다.
• 자물쇠 영역 내에서는
  • 열쇠의 돌기와 자물쇠의 홈이 정확히 일치해야 한다.
  • 열쇠 돌기와 자물쇠 돌기로는 열지 못한다.
  • 자물쇠의 모든 홈을 채워서 비어있는 곳이 없어져야 좌물쇠를 열 수 있다.

출처 : 코드 연구소

의사 결정

• 배열을 확장시켜서 열쇠를 이동, 회전 시키고, 자물쇠와 일치하는지 확인합니다.
• 확장시킨 배열에 자물쇠 배열의 값을 위치에 맞게 입력합니다.
• 열쇠를 이동시키면서 자물쇠에 맞는지 확인합니다.
• 열쇠가 맞지 않는다면 시계 방향으로 90도 회전시키면서 확인합니다. (총 4번 반복)

 

코드 구현

1. 열쇠와 자물쇠의 길이를 사용해 배열을 확장

자물쇠의 길이 + (열쇠의 길이-1) *2 의 크기로 배열 map[][]을 생성합니다.

int m = key.length;
int n = lock.length;

int len = m + (n-1) * 2; 

int[][] map = new int[len][len];

 

 

2. map에 자물쇠 위치 표시

map의 정 가운데에 자물쇠 돌기와 홈의 위치를 표시합니다.

for(int i=m-1 ; i<n+m-1 ; i++) {
    for(int j=m-1 ; j<n+m-1 ; j++) {
        map[i][j] = lock[i-(m-1)][j-(m-1)];
    }
}

 

3. 열쇠가 자물쇠에 맞는지 확인

map 배열과 key 배열, lock의 길이를 인자로 보내고, check 함수에서 열쇠가 자물쇠에 일치하는지 확인합니다.

일치하지 않으면 key를 회전(90도, 180도, 270도, 360도) 시켜서 일치 여부를 확인합니다.

 for(int i=0 ; i<4 ; i++) {
    if(check(map, key, n)) {
        return true;
    }
    rotate(key);
}
return false;

 

 

check 함수

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에 더함
                for(int k=0 ; k<keyLen ; k++) {
                    for(int l=0 ; l<keyLen ; l++) {
                        map[i+k][j+l] += key[k][l];
                    }
                }
                
                // 자물쇠 부분의 상태를 확인
                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; // 열쇠가 맞으면 true 반환
                
                // 다음 위치에 열쇠를 배치하기 위해 
                // map에 현재 배치된 열쇠 값을 빼서 원래 상태 복구
                for(int k=0 ; k<keyLen ; k++) {
                    for(int l=0; l<keyLen; l++){
                        map[i+k][j+l] -= key[k][l];
                    }
                }
            }
        }
        return false; // 열쇠가 맞지 않으면 false를 반환
    }

 

rotate 함수

 

기존 key 배열

0, 0	0 ,1	0,2
1,0	1,1	1,2
2,0	2,1	2,2

 

90도 회전 후 key 배열

2, 0	1 ,0	0,0
2,1	1,1	0,1
2,2	2,1	0,2

 

0,0 -> 0,2 로, 0,1 ->1,2 로, 0,2 -> 2,2 로 이동했습니다. 이렇게 식을 생각해보면 90도 회전 후

key[i][j] = 기존의 key[j][key길이-i-1] 입니다.  회전 점화식을 사용해서 회전 후의 key 배열을 구합니다.

 public static void rotate(int[][] key) {
    int len = key.length;
    int[][] temp = new int[len][len];

    // 시계 방향으로 회전시킨 key 배열을 temp 배열에 저장
    for(int i=0 ; i<len ; i++) {
        for(int j=0 ; j<len ; j++) {
            temp[i][j] = key[j][len-i-1];
        }
    }

    // temp 배열을 key 배열에 다시 저장
    for(int i=0 ; i<len ; i++) {
        for(int j=0 ; j<len ; j++) {
            key[i][j] = temp[i][j];
        }
    }
}

 

 

 

전체 코드

class Solution {
    public boolean solution(int[][] key, int[][] lock) {   
        int m = key.length;
        int n = lock.length;
        
        int len = m + (n-1) * 2; 
        
        int[][] map = new int[len][len];
        
        // map에 lock 표시
        for(int i=m-1 ; i<n+m-1 ; i++) {
            for(int j=m-1 ; j<n+m-1 ; j++) {
                map[i][j] = lock[i-(m-1)][j-(m-1)];
            }
        }
        
        // key가 lock에 맞는지 확인
        for(int i=0 ; i<4 ; i++) {
            if(check(map, key, n)) {
                return true;
            }
            rotate(key);
        }
        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++) {
                
                // key를 map에 입력해서 비교
                for(int k=0 ; k<keyLen ; k++) {
                    for(int l=0 ; l<keyLen ; l++) {
                        map[i+k][j+l] += key[k][l];
                    }
                }
                
                boolean flag = true;
                // lock이 전부 1이 됐는지 확인
                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) {
                            flag = false;
                            break;
                        }
                    }
                    if(!flag) break;
                }
                if(flag) return true;
                
                // map 상태를 원상 복구
                for(int k=0 ; k<keyLen ; k++) {
                    for(int l=0; l<keyLen; l++){
                        map[i+k][j+l] -= key[k][l];
                    }
                }
            }
        }
        return false;
    }
    
    public static void rotate(int[][] key) {
        int len = key.length;
        int[][] temp = new int[len][len];
        
        // 시계 방향으로 회전시킨 key 배열을 temp 배열에 저장
        for(int i=0 ; i<len ; i++) {
            for(int j=0 ; j<len ; j++) {
                temp[i][j] = key[j][len-i-1];
            }
        }
        
        // temp 배열을 key 배열에 다시 저장
        for(int i=0 ; i<len ; i++) {
            for(int j=0 ; j<len ; j++) {
                key[i][j] = temp[i][j];
            }
        }
    }
}