[프로그래머스]2020카카오블라인드:자물쇠와열쇠(java)

문제보러가기

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

 

이문제는... 어려웠다. 문제 자체는 이해하기에 어렵지 않았지만 단순 시물레이션이라기엔 배열에 대한 인덱스 지식과 더불어 깊은 복사 얕은 복사에 대한 지식을 갖고 있어야 가능한 문제였다고 생각한다.

 

이문제를 풀면서,, 2차원 배열에 대해 다시 한번 생각하게 되었다. 패딩 시킨다면 얼마큼...? 어디까지 가야 하지..? 인덱스 몇까지..? 뭐 이런 고민들을 하면서 많이 접해보고 다양한 시각으로 여러 문제들을 풀어봐야겠다고 생각했다!!

 

 

 

 

 

 

문제풀이

-문제의 핵심은 key, lock을 패딩 시키는 것이다. (lock과 겹치지 않는 key의 돌기는 상관하지 않기 때문)

-lock이 가운데에 있고 key가 회전, 이동하면서 lock에 해당하는 인덱스를 다 1로 채우는지를 판단하면 된다.

-90도씩 회전하는 코드 ratateKey [j][key.length-1-i] = key [i][j]; 

-패딩 인덱스 아래 사진처럼 되기 때문에 패딩 된 배열을 아래와 같이 만들 수 있다.

int [][] padMap = new int [lock.length+2*key.length-2][lock.length+2*key.length-2]

             

 

-key 역시 회전 후 패딩 시켜서 그 안에서 1에 해당하는 배열들을 수평(오른쪽 이동) 수직(아래쪽 이동) 시켜가며 lock에 해당하는 부분이 열리는지 확인한다

-열리지는 확인하기 위해 패딩 된 key와 lock을 합칠 때 각각 더해서 lock부분의 모든 인덱스가 1이 되면 자물쇠를 풀 수 있다고 본다.

 

class Solution {
    public boolean solution(int[][] key, int[][] lock) {
  
		int[][] rotateKey;
		int[][] padMap = new int[lock.length + 2 * key.length - 2][lock.length + 2 * key.length - 2];

		for (int i = 0; i < lock.length; i++) {
			for (int j = 0; j < lock[0].length; j++) {
				padMap[i + key.length - 1][j + key.length - 1] = lock[i][j];
			}
		}

		//회전 0,90,180,270도
		for (int i = 0; i < 4; i++) {
			rotateKey = new int[key.length][key.length];
			if (i != 0) {
				for (int j = 0; j < key.length; j++) {
					for (int k = 0; k < key.length; k++) {
						rotateKey[k][key.length-1-j] = key[j][k];
				
					}
				}
			}else {
				rotateKey = new int[key.length][key.length];
				for (int j = 0; j < key.length; j++) {
					System.arraycopy(key[j], 0, rotateKey[j], 0, key.length);
				};
			}
			for (int j = 0; j < key.length; j++) {
				System.arraycopy(rotateKey[j], 0, key[j], 0, key.length);
			}
			//key패딩시키기
			int[][] padKey = padding(rotateKey, lock.length);
			if (unlock(padMap, padKey,lock.length,key.length)) {
				return true;
			}
			// 수평이동
			for (int j = 1; j < padMap.length; j++) {
				int[][] moveKey = move(padKey, j);
				
				if (unlock(padMap, moveKey,lock.length,key.length)) {
					return true;
				}
				// 수직이동
				for (int k = 0; k < padMap.length; k++) {
					moveKey = move(moveKey, 0);
	
					if (unlock(padMap, moveKey,lock.length,key.length)) {
						return true;
					}
				}
			}

		}
		return false;

	}
	//키 이동시키기
	static int[][] move(int[][] key, int vOrH) {
		int[][] moveKey = new int[key.length][key.length];
		// 수평
		if (vOrH != 0) {
			for (int i = 0; i < key.length; i++) {
				for (int j = 0; j < key.length; j++) {
					if (j + vOrH < key.length && key[i][j] == 1) {
						moveKey[i][j + vOrH] = 1;
					}
				}
			}
		}
		// 수직
		else {
			for (int i = 0; i < key.length; i++) {
				for (int j = 0; j < key.length - 1; j++) {
					if (i+1<key.length && key[i][j] == 1) {
						moveKey[i + 1][j] = 1;
					}
				}
			}
		}
		return moveKey;

	}
	//key확장시키기
	static int[][] padding(int[][] key, int lockSize) {
		int[][] padKey = new int[lockSize + 2 * key.length - 2][lockSize + 2 * key.length - 2];
		for (int i = 0; i < key.length; i++) {
			for (int j = 0; j < key.length; j++) {
				padKey[i][j] = key[i][j];
			}
		}
		return padKey;
	}
	
    //패딩이된 key와 lock 합치고 풀렸는지 확인
	static boolean unlock(int[][] key, int[][] map,int lockSize,int keySize) {
		int[][] addMap = new int[map.length][map.length];

		// 합치기
		for (int i = 0; i < addMap.length; i++) {
			for (int j = 0; j < addMap.length; j++) {
				addMap[i][j] = key[i][j] + map[i][j];
			}
		}
		// 잠금이 풀렸는지 -> lock에 해당하는 부분이 다 1인지
		for (int i = 0; i < lockSize; i++) {
			for (int j = 0; j < lockSize; j++) {
				if(addMap[i + keySize - 1][j + keySize - 1]!=1)
					return false;
			}
		}
		return true;
	}



}