프로그래머스 자물쇠와 열쇠 자바 풀이

문제 링크

문제 풀이 시간 : 1시간 20분

문제 요약

key는 M×M 크기의 2차원 배열
lock은 N×N 크기의 2차원 배열
열쇠를 회전 및 이동시켜 자물쇠의 홈을 돌기로 정확히 채우고, 돌기끼리 겹치지 않도록 해야 한다.
자물쇠의 모든 홈이 채워지면 true, 아니면 false를 반환한다.

문제 풀이

잘못된 시도

문제의 조건을 처음 봤을 때, 완전 탐색으로 모든 경우를 확인해야 한다는 생각이 들었다.

그래서 처음에는 아래 그림처럼,

lock 배열의 왼쪽 위부터 key 배열의 오른쪽 아래를 차례로 맞춰보며,

마지막에는 lock의 오른쪽 아래와 key의 왼쪽 위를 비교하는 방식으로 구현하려 했다.

하지만 코드를 작성하면 할수록

조건문이 너무 많아지고, 코드가 복잡해져서 가독성이 급격히 떨어졌다.

경계 처리가 너무 복잡해지면서, 도대체 내가 뭘 비교하고 있는지도 헷갈릴 정도로 꼬여버렸다.

정답 시도

그래서 생각한 방법이 밑의 사진처럼 lock 배열을 확장시켜서 비교를 좀 더 편하게 해주는 것이었다.

이렇게 하면 경계 조건을 신경 쓸 필요가 없고 key를 단순히 슬라이드시키면서 더하거나 빼기만 해도모든 위치를 쉽게 탐색할 수 있다.

왜 확장할까

기존에는 key가 lock 밖으로 벗어나는 경우를 일일이 조건문으로 처리해야 했다.

하지만 lock을 (M-1)칸씩 상하좌우로 확장하면,

key가 완전히 자물쇠 밖에 있을 때까지 한 번에 이동시킬 수 있다.

즉,

확장된 match 배열의 크기는 n + (m-1)*2,
실제 자물쇠 영역은 그 안의 가운데 N×N 구간이다.

이 구조를 사용하면, “자물쇠가 모두 1로 채워졌는지” 확인하는 것도 그 가운데 구간만 검사하면 되므로 훨씬 단순해진다.

회전 처리

java

public int[][] rotate(int[][] key){
    int[][] temp = new int[m][m];
    for(int i=0;i<m;i++){
        for(int j=0;j<m;j++){
            temp[j][m-1-i] = key[i][j];
        }
    }
    return temp;
}

이 회전 함수는 시계 방향 90도 회전을 구현한다.

2차원 배열의 (i, j) 좌표를 회전하면, 새로운 좌표는 (j, M-1-i)가 된다.

즉,

기존 행 인덱스 i는 새로운 열 인덱스로,
기존 열 인덱스 j는 뒤에서부터 세는 행 인덱스로 바뀌는 것이다.

이 공식을 그대로 코드에 옮기면 위와 같은 형태가 된다.

최종 코드

java

class Solution {
    public int[][] match;
    public int n,m;
    
    public boolean check(){
        for(int i=m-1;i<n+m-1;i++){
            for(int j=m-1;j<n+m-1;j++)
                if(match[i][j]!=1)
                    return false;
        }
        return true;
    }
    
    public int[][] rotate(int[][] key){
        int[][] temp = new int[m][m];
        for(int i=0;i<m;i++){
            for(int j=0;j<m;j++){
                temp[j][m-1-i] = key[i][j];
            }
        }
        return temp;
    }
    
    public boolean solution(int[][] key, int[][] lock) {
        boolean answer = false;
        
        n = lock.length;
        m = key.length;
        
        match = new int[n+(m-1)*2][n+(m-1)*2];
        for(int i=m-1;i<n+m-1;i++){
            for(int j=m-1;j<n+m-1;j++){
                match[i][j] = lock[i-(m-1)][j-(m-1)];
            }
        }
        
        //4방향 회전
        for(int i=0;i<4;i++){
            for(int j=0;j<n+m-1;j++){
                for(int k=0;k<n+m-1;k++){
		                //key 더하기
                    for(int a=0;a<m;a++){
                        for(int b=0;b<m;b++){
                            match[j+a][k+b] += key[a][b];
                        }
                    }
                    //key가 맞는지 검사
                    if(check())
                        return true;
                        
                    //아니면 다시 빼주기
                    for(int a=0;a<m;a++){
                        for(int b=0;b<m;b++){
                            match[j+a][k+b] -= key[a][b];
                        }
                    }
                }
            }
            //키 회전
            key = rotate(key);
        }
        
        return answer;
    }
}

자물쇠와 열쇠

문제 풀이 시간 : 1시간 20분

문제 요약

문제 풀이

잘못된 시도

정답 시도

왜 확장할까

회전 처리

최종 코드

함께 읽으면 좋은 글

택배상자

롤케이크 자르기

할인 행사

숫자 변환하기