[프로그래머스] 카카오_자물쇠와 열쇠 (자바 풀이)

문제

https://programmers.co.kr/learn/courses/30/lessons/60059?language=java 

코딩테스트 연습 - 자물쇠와 열쇠

 

풀이

이 문제는 배열을 확장시켜서 풀면 쉽게 해결할 수 있다. 

 

[그림 1] 해결법

위와 같이 배열을 확장시켜서 차례대로 자물쇠와 키를 맞춰보면 된다.

 

이때 배열을 얼마나 확장시켜야 할까? 잘 보면 "자물쇠의 길이 + (키의 길이*2) - 2"만큼 확장시키면 된다는 것을 알 수 있다.

 

따라서 해결 과정은 다음과 같다.

 

1. "자물쇠의 길이 + (키의길이*2) - 2" 크기의 배열 map[][]을 만든다.

2. map에 lock 배열의 값을 위치에 맞게 입력한다.

3. 키가 자물쇠에 맞는지 체크한다.

4. 키가 안 맞다면 시계 방향으로 90도 회전시키고 확인한다. (총 4번 반복)

 

자세한 내용은 코드를 참고하자.

 

코드

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];
            }
        }
        
    }
}

 

결과