Today I Learned

오늘은 구현 문제를 풀어보았다.

자물쇠와 열쇠

https://school.programmers.co.kr/learn/courses/30/lessons/60059

문제

N x N짜리 key와 M x M짜리 lock이 주어진다. key는 회전과 이동이 가능하다. N<=M이다. lock의 모든 칸이 1이어야 자물쇠가 풀린다. 주어진 조건에서 key로 lock을 풀 수 있는지 구해라.

풀이 과정

1. 우선 key를 회전하는 방법을 먼저 구현한다. 새로 이차원 배열을 하나 만든다. 90도로 회전을 하게 되면 (i,j)가 (배열길이-1-j, i)로 바뀐다. 이중 for문으로 구현해 회전된 배열을 반환한다.

2. key와 lock을 매개변수로 받아 서로 잘 맞물리는지 확인하는 메서드를 만든다. 키의 오른쪽아래 구석이 lock의 왼쪽위구석부터 맞물리게 체크한 다음 전체를 순회해 키의 왼쪽위구석이 lock의 오른쪽 아래 구석까지 순회하면서 체크해야 한다.

3. x,y값은 key가 lock위에서 움직이는 좌표를 의미한다. -n~n-1까지 움직인다. x좌표와 y좌표 둘다 움직이기 때문에 solution 메서드에서 이중 for문으로 x,y좌표를 넣어준다.

4. solution은 (회전-이동)의 절차가 총 4번(90도 회전이므로) 이루어지므로 4번의 for문 안에서 실행된다.

5. isCorrect에서 key의 이동 결과 key 범위 밖에 있는 lock에 0값이 있으면 자물쇠가 풀리지 않으므로 0을 반환한다. 범위 안이라면 key와 lock의 값이 달라야 자물쇠가 풀리므로 같으면 false를 반환하게 한다. false가 없으면 최종적으로 true를 반환한다.

Trouble

• 특별한 알고리즘이나 자료구조는 필요가 없었다.

• 하지만 구현문제인만큼 발상과 구현 과정 자체에 꽤 오랜 시간이 걸렸다.

• 회전은 바로 풀었지만 이동과정이 생각보다 번거로웠다. 매칭 여부를 따로 메서드로 파서 그걸 solution 메서드에서 이동 좌표를 넣어줘서 풀 수 있었다.

Java 코드

class Solution {
    public boolean solution(int[][] key, int[][] lock) {
        for(int i=0;i<4;i++){
            key = rotate(key);
            int n = lock.length-1;
            for(int x=-n;x<n; x++){
                for(int y=-n;y<n; y++){
                    if(isCorrect(key,lock,x,y)) return true;
                }
            }
        }
        return false;
    }
    
    int[][] rotate(int[][] key){
        int l = key.length;
        int[][] result = new int[l][l];
        for(int i=0;i<l;i++){
            for(int j=0;j<l;j++){
                result[i][j] = key[key.length-1-j][i];
            }
        }
        return result;
    }
    
    boolean isCorrect(int[][] key, int[][] lock, int x, int y){
        int m = lock.length;
        int n = key.length;
        
        for(int i=0;i<m;i++){
            for(int j=0;j<m;j++){
                if(i+x<0 || i+x>=n || j+y<0 || j+y>=n){
                    if(lock[i][j]==0) return false;
                }else{
                    if(lock[i][j] == key[i+x][j+y]) return false;   
                }
            }
        }
        return true;
    }
}