[프로그래머스] 자물쇠와 열쇠

문제 풀이

문제 설명은 다음 링크를 참조하자.

우선 key를 90도 단위로 회전한 배열을 반환하는 rorate 함수를 선언한다.

public int[][] rotate(int[][]key, int degree){
    int[][] rotated = new int[key.length][key.length];

    for(int i = 0;i < key.length;i++){
        for(int j = 0;j < key.length;j++){
            if(degree == 0)
                rotated[i][j] = key[i][j];
            if(degree == 90)
                rotated[j][key.length - 1 - i] = key[i][j];
            if(degree == 180)
                rotated[key.length- 1 - i][key.length- 1 - j] = key[i][j];
            if(degree == 270)
                rotated[key.length - 1 - j][i] = key[i][j];
        }
    }

    return rotated;
}

그 다음 key를 평행이동하면서 lock에 맞출 수 있는지를 판단하는 canMatch 메서드를 선언한다. key를 세로 방향으로 rowStart, 가로 방향으로 colStart 만큼 평행이동 시킨다.

그 다음 lock과 key가 겹치는 곳에서는 두 element를 합치고, 겹치지 않는 경우 lock의 값만 관찰한다. 관찰하는 값이 1이 아닌 경우(0이나 2인 경우), 해당 rowStart, col의 경우 제대로 맞물리지 않는 것으로 판단하여, 다음 rowStart, colStart의 값으로 바꾼다.

맞물리는 rowStart, colStart가 하나라도 존재하면 true, 아니면 false를 반환한다.

public boolean canMatch(int[][] key, int[][] lock){
    for(int rowStart = -(key.length - 1);
        rowStart <= lock.length - 1;
        rowStart++){
  loop: for(int colStart = -(key.length - 1);
            colStart <= lock.length - 1;
            colStart++){
             for(int i = 0;i < lock.length;i++){
                for(int j = 0;j < lock.length;j++){
                    int sum;
                    try{
                        sum= lock[i][j] + key[i - rowStart][j - colStart];
                    }catch (ArrayIndexOutOfBoundsException e){
                        sum = lock[i][j];
                    }

                    if(sum != 1) continue loop;
                }
            }
            return true;
        }
    }

    return false;
}

이렇게 두 메서드를 정의하면 0, 90, 180, 270도 회전했을 때에 대하여 하나라도 맞물리는지 확인하면 되므로 solution 메서드를 간단하게 작성할 수 있다.

public boolean solution(int[][] key, int[][] lock) {

    return canMatch(key, lock) ||
           canMatch(rotate(key, 90), lock) ||
           canMatch(rotate(key, 180), lock) || 
           canMatch(rotate(key, 270), lock);
}