[프로그래머스(Programmers)][자바(java)] (Lv3) 자물쇠와 열쇠

 

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

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

 

문제 요약

• 열쇠로 자물쇠를 열수 있으면 true를, 열 수 없으면 false를 return 하는 문제
• 자물쇠는 N x N 크기의 정사각 격자 형태 ( 격자 한 칸의 크기가 1 x 1 )
• 열쇠는 M x M 크기인 정사각 격자 형태
  ( N, M은 자연수 ) ( 3 ≤ M ≤ 20, 3 ≤ N ≤ 20, M <= N  )
• 자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있음
• 열쇠는 회전과 이동이 가능, 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조
  ( 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있음 )
• 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만,
  자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며
  열쇠의 돌기와 자물쇠의 돌기가 만나서는 안 됨

 

문제 풀이

*  완전 탐색

-  자물쇠에서 홈이 존재하는 전체 범위를 직사각 형태로 구하고 그 값을 배열에 담음
   -  세로 시작 인덱스  :  lhis ( lock_hole_i_start )
   -  세로 끝 인덱스  :  lhie ( lock_hole_i_end )
   -  세로 길이  :  lhv ( lock_hole_vertical )  = lhie - lhis + 1
   -  가로 시작 인덱스  :  lhjs ( lock_hole_j_start )
   -  가로 끝 인덱스  :  lhje ( lock_hole_j_end )
   -  가로 길이  :  lhh ( lock_hole_horizontal )  = lhje - lhjs + 1
 ( 자물쇠 홈의 범위( lhv x lhh )가 열쇠 크기( M x M )보다 크면 열쇠가 자물쇠의 모든 홈을 채울 수 없으므로 열 수 없음 ==> return false )
 ( 자물쇠 홈의 범위( lhv x lhh )의 값( 0 or 1 )을 배열 int l[lhv*lhh]  에 차례로 담음 )

-  열쇠에서 그 범위 내에 자물쇠의 홈과 열쇠의 돌기가 맞닿는( 값이 서로 반대인 0 <-> 1 ) 모양이 있는지 탐색하는 함수 isOpenable()  정의 후 함수 수행

-  열쇠를 나타내는 2차원 배열을 90˚씩 회전하는 rotateArr()  함수를 정의하고 수행하여 배열들을 3차원 배열 int key_r[3][m][m]  에 넣고 총 4번씩 비교
 ( 원래 key( 0˚ ) + 회전 3번( 90˚, 180˚, 270˚ ) )

public class Solution {
	
	public int[][] rotateArr( int[][] o, int m ) {
		int i, j;
		int r[][] = new int[m][m];  // rotated, original
		for( i = 0; i < m; i++ )
			for( j = 0; j < m; j++ )
				r[i][j] = o[m-j-1][i];
		return r;
	}

	public boolean isOpenable( int[][] k, int[] l, int m, int lhv, int lhh ) {
		int i, j, v, h, idx;
		for( v = 0; v <= m-lhv; v++ ) {
			loop:
			for( h = 0; h <= m-lhh; h++ ) {
				idx = 0;
				for( i = v; i < v+lhv; i++ )
					for( j = h; j < h+lhh; j++ )
						if( k[i][j] == l[idx++] ) 
							continue loop;
				return true;
			}
		}
		return false;
	}
	
	public boolean solution( int[][] key, int[][] lock ) {
		int n = lock.length, m = key.length, i, j;
		int lhv, lhh, lhis = n-1, lhie = 0, lhjs = n-1, lhje = 0;
        // lock_hole_vertical/horizontal, lock_hole_i_start/end, lock_hole_j_start/end
		for( i = 0; i < n; i++ ) {
			for( j = 0; j < n; j++ ) {
				if( lock[i][j] == 0 ) {
					lhis = lhis > i ? i : lhis;
					lhie = lhie < i ? i : lhie;
					lhjs = lhjs > j ? j : lhjs;
					lhje = lhje < j ? j : lhje;
				}
			}
		}
		lhv = lhie - lhis + 1;
		lhh = lhje - lhjs + 1;
		if( m < Math.max( lhv, lhh ) )
			return false;
		int l[] = new int[lhv*lhh], idx = 0;
		for( i = lhis; i < lhis+lhv; i++ )
			for( j = lhjs; j < lhjs+lhh; j++ ) 
				l[idx++] = lock[i][j];
		if( isOpenable( key, l, m, lhv, lhh ) )
			return true;
		int key_r[][][] = new int[3][m][m];  // 90, 180, 270 (counterclockwise) 
		key_r[0] = rotateArr( key, m );
		for( i = 1; i < 3; i++ )
			key_r[i] = rotateArr( key_r[i-1], m );
		for( i = 0; i < 3; i++ ) 
			if( isOpenable( key_r[i], l, m, lhv, lhh ) )
				return true;
		return false;
	}
}