프로그래머스 - [Level 3] 자물쇠와 열쇠(JAVASCRIPT)
카테고리 : 완전 탐색
모든 경우의 수를 탐색해 답을 찾는 문제이다.
풀이과정은 다음과 같다.
1) 새로운 자물쇠 배열을 만든다.(60 x 60)
자물쇠 배열의 최대 크기 (20 x 20)
키 배열의 최대 크기 (20 x 20)
이기 때문에 키 배열을 놓을 수 있는 공간의 배열을 만든다.
2) (0,0) 부터 (자물쇠 배열 max_y, 자물쇠 배열 max_x)
를 키 배열의 '시작점'으로 잡고 탐색한다.
매 '시작점'마다 4회 rotate를 반복해주며,
자물쇠가 열리는지 판단한다.
키 배열을 '0'
자물쇠 배열을 [1]
위치가 겹치는 부분을 [2]
라고 했을 때,
시작점 (0,0)
'0''0'
'0'[2][1]
[1][1]
시작점 (0,1)
'0''0'
[2][2]
[1][1]
시작점 (0,2)
'0''0'
[1][2]'0'
[1][1]
시작점 (1,0)
'0'[2][1]
'0'[2][1]
.
.
.
시작점 (자물쇠 배열 max_y , 자물쇠 배열 max_x)
[1][1]
[1][2]'0'
'0''0'
이러한 방식으로 탐색을 하는 것이다.
실패코드
로직상 문제는 없어보였는데 계속 실패했다.
이유는 'call by reference' 때문이었다.
이 때문에 자물쇠 배열에 계속 값이 누적되었다.
항상 true 만을 반환해 1번 , 23 ~33번 테스트 케이스에서
계속 '실패'가 떴다.(1번, 23 ~ 33번은 false가 정답)
call by value 타입
- number, string, boolean
call by reference 타입
- array, object, date
function check(i,j,key,arr,len){
for(var y=0;y<key.length;y++){
for(var x=0;x<key.length;x++){
arr[y+i][x+j]+=key[y][x];
}
}
for(var y=19;y<19+len;y++){
for(var x=19;x<19+len;x++){
if(arr[y][x]===0 || arr[y][x]===2) return false;
}
}
return true;
}
function solution(key, lock) {
var arr = Array.from(Array(60), () => new Array(60).fill(0));
for(var i=0;i<lock.length;i++){
for(var j=0;j<lock.length;j++){
arr[i+19][j+19]=lock[i][j];
}
}
for(var i=0;i<19+lock.length;i++){
for(var j=0;j<19+lock.length;j++){
for(var dir=0;dir<4;dir++){
if(check(i,j,key,arr,lock.length)) return true;
var tmp=Array.from(Array(key.length),()=>new Array(key.length).fill(0));
for(var y=0;y<key.length;y++){
for(var x=0;x<key.length;x++){
tmp[y][x]=key[x][key.length-y-1];
}
}
for(var y=0;y<key.length;y++){
for(var x=0;x<key.length;x++){
key[y][x]=tmp[y][x];
}
}
}
}
}
return false;
}
성공 코드
call by reference로 넘어온 arr 배열을
deep copy를 통해 새로운 배열을 만들고,
비교해줬더니 '통과'됐다.
여기서 한 가지 중요한 개념은
deep copy(깊은 복사) vs shallow copy(얕은 복사)이다.
// check 함수 탐색을 위해, deep copy를 해주자.
function deepCopy(arr){
var newarr=Array.from(Array(arr.length),()=>new Array(arr.length).fill(0));
for(var y=0;y<arr.length;y++){
for(var x=0;x<arr.length;x++){
newarr[y][x]=arr[y][x];
}
}
return newarr;
}
/**
자물쇠가 열리는지 판단해준다.
자물쇠 배열 범위에 맞게 key값을 더해준다.
그리고 자물쇠 배열 값이 1이 아니면 false를 return 해준다.
**/
function check(i,j,key,arr,len){
var newarr=deepCopy(arr);
for(var y=0;y<key.length;y++){
for(var x=0;x<key.length;x++){
newarr[y+i][x+j]+=key[y][x];
}
}
for(var y=19;y<19+len;y++){
for(var x=19;x<19+len;x++){
if(newarr[y][x]===0 || newarr[y][x]===2) return false;
}
}
return true;
}
// key 배열 회전 call by reference
function rotate(key){
var tmp=Array.from(Array(key.length),()=>new Array(key.length).fill(0));
for(var y=0;y<key.length;y++){
for(var x=0;x<key.length;x++){
tmp[y][x]=key[x][key.length-y-1];
}
}
for(var y=0;y<key.length;y++){
for(var x=0;x<key.length;x++){
key[y][x]=tmp[y][x];
}
}
}
function solution(key, lock) {
// 60 x 60 배열
var arr = Array.from(Array(60), () => new Array(60).fill(0));
for(var i=0;i<lock.length;i++){
for(var j=0;j<lock.length;j++){
arr[i+19][j+19]=lock[i][j];
}
}
// (0,0) => 자물쇠 마지막 좌표를 시작점으로 잡고 탐색해준다.
for(var i=0;i<19+lock.length;i++){
for(var j=0;j<19+lock.length;j++){
for(var dir=0;dir<4;dir++){
if(check(i,j,key,arr,lock.length)) return true;
rotate(key); // call by reference
}
}
}
return false;
}
통과를 했지만 시간효율을 보니 뭔가 찜찜하다.
다른 사람의 코드
차이
1)
내 코드는 매 좌표마다 rotate를 해줬다면
이 코드는 매 좌표마다 rotate하지 않고,
먼저 모든 좌표에 대해 탐색한 후 rotate 하는 방식으로 구현했다.
2)
deep copy로 배열을 생성하지 않고,
mark를 +1 한 후 lock 체크
체크 후, 다시 mark를 -1 해주는 백트래킹 방식으로 구현했다.
for(let y=0; y<keyLen ;y++){
for(let x=0; x<keyLen ;x++){
maps[y + offsetY][x + offsetX] += key[y][x]*mark;
}
}
function solution(key, lock) {
const keyLen = key.length;
const lockLen = lock.length;
const mapLen = (keyLen)*2 + lockLen-2;
const mapGen = len => Array(len).fill(0).map(_=>Array(len).fill(0));
const maps = mapGen(mapLen);
// insert lock
for(let i=0;i<lockLen;i++){
for(let j=0;j<lockLen;j++){
const offset = keyLen - 1;
maps[offset+i][offset+j] = lock[i][j];
}
}
// only rectangle
// not clone
function rotate(arr) {
const arrLen = arr.length;
const arrLenHalf = Math.ceil(arrLen / 2);
for (let i = 0; i < arrLenHalf; i++) {
for (let j = i; j < arrLen - i - 1; j++) {
const temp = arr[i][j];
const offset = arrLen - i - 1;
arr[i][j] = arr[offset - j + i][i];
arr[offset - j + i][i] = arr[offset][offset - j + i];
arr[offset][offset - j + i] = arr[j][offset];
arr[j][offset] = temp;
}
}
}
function isAnswer(){
let res = true;
for(let i=0;i<lockLen;i++){
for(let j=0;j<lockLen;j++){
const offset = keyLen-1;
if(maps[offset+i][offset+j] % 2 == 0){
return false;
}
}
}
return true;
}
function mapMark(offsetY, offsetX, mark){
for(let y=0; y<keyLen ;y++){
for(let x=0; x<keyLen ;x++){
maps[y + offsetY][x + offsetX] += key[y][x]*mark;
}
}
}
function unLock(){
const canMoveSize = mapLen - keyLen + 1;
for(let i=0;i < canMoveSize ;i++){
for(let j=0;j < canMoveSize ;j++){
const offsetY = i;
const offsetX = j;
mapMark(offsetY,offsetX, 1);
if(isAnswer()) return true;
mapMark(offsetY,offsetX, -1);
}
}
return false;
}
if(unLock()) return true;
rotate(key);
if(unLock()) return true;
rotate(key);
if(unLock()) return true;
rotate(key);
if(unLock()) return true;
return false;
}
Referecne
- http://changpd.blogspot.com/2014/05/javascript-call-by-reference.html
Leave a comment