LEVEL 3 : 자물쇠와 열쇠

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

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

 

• 문제

  • 

    문제 1

  • 예시

    • 

      예시

    • 

      입출력

    • key를 시계 방향으로 90도 회전하고, 오른쪽으로 한 칸, 아래로 한 칸 이동하면 lock의 홈 부분을 정확히 모두 채울 수 있습니다.

 

---

풀이

• 완전 탐색 문제 이다(모든 경우의 수를 전부 다 대입)
  
  • Padding 부분이 너무 어려워서 다른 사람 코드를 참고했습니다ㅠㅠ
• 최대 회전이 4번까지 가능하므로 4 * M * M 배열을 생성합니다
  • [0] 번째는 입력받은 키 그대로
  • [1] 번째는 [0]번째를 90도 회전
  • [2] 번째는 [1]번째를 90도 회전
  • [3] 번째는 [2]번째를 90도 회전
  • Rotation 함수
    • 이전 값 배열을 받아와 90도로 회전합니다. 이때 90도로 회전하기 위해서는 행은 [ M - 1 - j] ,열은 [i] 로 고정시켜야 됩니다.
• lock의 크기 - 1 값을 SIZE 변수에 담는다( 현재 내 Key값에 SIZE * 2 만큼을 크기의 배열을 만들것이다)
• K for문 : 회전한 모든 경우의 수를 체크
  • PaddingKey = 키 배열의 이동을 실제로 이동시킬 필요없이 키와 자물쇠 배열이 서로 스쳐지나가는 것 처럼 하면 키가 이동하는 것 처럼 보일 것이다.

  • 

    설명

  • 한 구역을 흩었는데 같은 것이 없었다면 - true를 반환
  • 한 구역을 흩었는데 같은 것이 있다면 다음 구역 탐색

• public static boolean solution(int[][] key, int[][] lock) {
          int M = key.length; // M * M 임으로 크기를 가지고 온다
          int[][][] rotationKey = new int[4][M][M]; //최대 4개까지 회전이 가능하므로 4*M*M배열
          rotationKey[0] = key;//1번째는 회전 안한 상태
          for(int i = 1;i < 4; ++i){//2~4번째 회전 하기
              rotationKey[i] = Rotation(rotationKey[i-1],M);//이전꺼에서 90도 회전
          }
          int size = lock.length - 1;
          for(int k=0;k<4;++k){
              int[][] paddingKey = Padding(rotationKey[k],M,size); // 흩을구역 
              for(int i = 0 ; i < paddingKey.length - size; ++i) {
      			OUTER:for(int j = 0 ; j < paddingKey[0].length - size ; ++j) { 
                      int N = lock.length;
                      for(int R=0;R<N;++R){//LOCK만큼 돈다.
                          for(int C=0;C<N;++C){
                              if(paddingKey[R+i][C+j] == lock[R][C])//만약 키와 일치하는 부분이 있다면 불가능 하므로 다음구역 흩는다
                                  continue OUTER;
                          }   
                      }            
                      return true;//여기까지 왔다면 키와 일치하는 부분이 없는 구역이 존재하므로 true반환후 종료
                  }
              }
          }
          return false;
      }
      public static int[][] Rotation(int[][] key,int M){//회전 함수
          int[][] rotation = new int[M][M];
          for(int i=0;i<M;++i){
              for(int j=0;j<M;++j){
                  rotation[M - 1 - j][i] = key[i][j];//이전 위치에서 90도로 회전한다.
              }
          }
          return rotation;
      }
      public static int[][] Padding(int[][] key,int M,int N){
      
          int[][] padding = new int[M + N*2][M + N*2]; // M - SIZE ~ M + SIZE 까지 PADDING을 적용
          for(int i=0;i<M;++i){
              for(int j=0;j<M;++j){
                  padding[i+N][j+N] = key[i][j];
              }
          }
          return padding;
      }