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

 

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

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

약 7%의 정답률인 문제입니다.

완전 탐색으로 풀 수 있지만 어떻게 구현해야 할지 몰라서 많이 헤맸습니다.

 

자물쇠의 크기를 n에서 n+2*(m-1)로 늘려줍니다.

n = 3, m = 3 일때

파란색은 자물쇠의 범위, 초록색은 키의 범위입니다.

초록색을 한칸씩 이동해가며 자물쇠와 맞춰보는 것입니다.

단, 한칸씩 이동하며 검사를 할 때 키는 90도씩 회전하여 칸당 총 4번을 검사합니다.

 

키의 1과 자물쇠의 1이 겹치지 않는지 검사하고, 자물쇠의 모든 칸이 채워졌는지 검사합니다.

---

메소드

boolean solution

lock의 크기를 늘린 map, temp를 생성합니다.

map은 lock이 중앙에 위치한 초기 상태를 가지고, temp는 키를 자물쇠에 꽂은 상태를 반영합니다.

key는 한 칸씩 이동하며 회전을 합니다. temp에 map을 넣어주고 temp에 키를 꽂습니다.

키를 꽂은 후 자물쇠에 맞는지 검사를 해줍니다.

(rotate, setMap, check호출)

int[][] rotate

key를 시계방향으로 90도 회전한 후에 회전한 2차원 배열을 반환합니다.

int[][] setMap

키를 꽂은 temp를 기존의 map으로 세탁해줍니다.

clone()을 이용한 깊은 복사를 이용했습니다.

boolean check

자물쇠의 홈이 모두 채워졌는지 검사해줍니다.

 

public class pm자물쇠와열쇠 {
	
	public static void main(String[] args) {
		int key[][] = {{0,0,0},{1,0,0},{0,1,1}};
		int lock[][] = {{1,1,1},{1,1,0},{1,0,1}};
		solution(key, lock);
	}

	public static boolean solution(int[][] key, int[][] lock) {
		int n = lock.length;
		int m = key.length;

		int map[][] = new int[n + 2*(m-1)][n + 2*(m-1)];
		int temp[][] = new int[map.length][map.length];

		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) 
				map[m-1+i][m-1+j] = lock[i][j];
		}

		for(int i = 0; i <= map.length-m; i++) {
			for(int j = 0; j <= map.length-m; j++) {
				l:	for(int k = 0; k < 4; k++) {
					//key 회전
					key = rotate(key);
					//temp 세탁
					temp = setMap(map);

					//자물쇠에 키를 꽂음
					for(int x = 0; x < m; x++) {
						for(int y = 0; y < m; y++) {
							if(temp[i+x][j+y] == 1 && key[x][y] == 1)
								continue l;
							else if(temp[i+x][j+y] == 0 && key[x][y] == 1)
								temp[i+x][j+y] = 1;
						}
					}
					//자물쇠 검사
					if(check(temp, n, m))
						return true;
				}
			}
		}

		return false;
	}

	public static int[][] rotate(int key[][]) {
		int len = key.length;
		int convert[][] = new int[len][len];

		for(int i = 0; i < len; i++) {
			for(int j = 0; j < len; j++) {
				convert[j][len-i-1] = key[i][j];
			}
		}

		return convert;
	}

	public static int[][] setMap(int map[][]) {
		int len = map.length;
		int convert[][] = new int[len][len];

		for(int i = 0; i < len; i++) 
			convert[i] = map[i].clone();

		return convert;
	}
	
	public static boolean check(int map[][], int n, int m) {
		for(int i = m-1; i < n+m-1; i++) {
			for(int j = m-1; j < n+m-1; j++)
				if(map[i][j] == 0)
					return false;
		}
		
		return true;
	}

}