Programmers[60059] - 자물쇠와 열쇠[Level3]

링크

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

문제설명

• 열쇠를 돌리면서 자물쇠랑 맞물리면 풀린다

문제풀이

• 0, 90, 180, 270 도 회전을 한 열쇠를 하나하나 맞춰보면 된다.
• 회전은 전치행렬 + 좌우대칭하면 90도 회전이다. 사실 다른 규칙을 모르겠다...
• 열쇠를 하나하나 맞출때 경계검사 하나하나 하기 싫어서 padding(겉에 추가 행렬공한 만들어 줌) 작업을 했다.
  • Key : M^2
  • Lock : N^2
  • Padded Map : {(M-1) + N + (M-1)}^2

문제코드

public class Solution60059_자물쇠와_열쇠 {

    public static int M;
    public static int N;
    public static int P;
    public static int[][] pad;

    public static int[][] rotate(int[][] key) {
        int[][] temp = new int[M][M];
        int[][] ans = new int[M][M];
//        transpose
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < M; j++) {
                temp[i][j] = key[j][i];
            }
        }
//        좌우대칭
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < M; j++) {
                ans[i][j] = temp[i][M-1-j];
            }
        }

        return ans;
    }

    public static boolean solution(int[][] key, int[][] lock) {
        M = key.length;
        N = lock.length;
        P = N+(M-1)*2;

        pad = new int[P][P];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                pad[M-1+i][M-1+j]=lock[i][j];
            }
        }
        int[][] npad = new int[P][P];


        int[][] nkey = key.clone();

        for (int i = 0; i < 4; i++) {
//            열쇠 돌리고
            nkey = rotate(nkey);
//            돌린열쇠 하나하나씩 끼워맞춰보는 위치찾고
            for (int j = 0; j < M-1+N; j++) {
                for (int k = 0; k < M-1+N; k++) {
//                    npad 초기화
                    for (int pi = 0; pi < P; pi++) {
                        for (int pj = 0; pj < P; pj++) {
                            npad[pi][pj]=pad[pi][pj];
                        }
                    }

//                    끼워맞춰보기
                    for (int j_ = 0; j_ < M; j_++) {
                        for (int k_ = 0; k_ < M; k_++) {
                            npad[j+j_][k+k_] += nkey[j_][k_];
                        }
                    }
//                    다 맞는지 체크
                    int cnt = 0;
                    for (int j_ = 0; j_ < N; j_++) {
                        for (int k_ = 0; k_ < N; k_++) {
//                            열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다
                            if(npad[M-1+j_][M-1+k_]==1)cnt++;
                        }
                    }
                    if(cnt==N*N) {
                        return true;
                    }
                }
            }
        }

        return false;
    }
    public static void main(String[] args) {
        System.out.println(solution(new int[][] {{0, 0, 0}
                                                ,{1, 0, 0}
                                                ,{0, 1, 1}
        }
        ,                            new int[][] {{1, 1, 1}
                                                ,{1, 1, 0}
                                                ,{1, 0, 1}
        }));
    }
}

아쉬운 점

• 문제 제대로 안읽음
  • 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다
  • 그냥 ++하고 >0 체크했었음.
  • 1인지 아닌지 정확하게 체크했어야함
• 자물쇠 넣는 위치 바꿀때 마다 npad 초기화 안함
• 이차원 배열은 clone 쓰면 안되는듯..
  • reference를 그대로 가져가서 초기화가 안되는 것 같다.

잘한 점

• 회전하는법 어거지로 찾긴 함(전치 + 좌우대칭)
• Padding 생각했음
• 40분

다른 풀이

• 90도 회전하는 코드

  for (int i = 0; i < mat.length; i++)
     {
         for (int j = 0; j < mat.length; j++)
         {
             temp[i][j] = mat[mat.length - j - 1][i];
         }
     }

  이런게 있더라

• 90도 회전 : (x,y) -전치-> (y,x) -좌우대칭-> (N-1-y,x)
• 이런식으로
• 180도 회전 : (x,y) -> (N-1-x,N-1-y)