프로그래머스: 자물쇠와 열쇠 - javascript(단순 구현)

문제 출처 

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

프로그래머스

 

문제 풀이 

이런 문제는 시간을 두고 본인이 해결할 때까지 다른 사람이 푼 코드를 보지 않는다면 좋겠다. 

어떤 특별한 알고리즘이 필요한 것이 아니라서,, 

자기가 끈질기게 구현해보는 연습을 할 수 있는 좋은 문제인 것 같다. 

 

하지만 이 정도의 아이디어는 얻고 혼자 풀면 좋을 것 같은데 

아래 그림과 같이 주어진 lock을 가로, 세로 3배씩 확장시킨 그래프로 생각하는 것이다. 

그래서 거기서 key 그래프가 이동과 회전을 하면서 lock을 풀 수 있으면 된다. 

 

 

 

 

코드 풀이 시작 

## 1. lock_graph 생성 및 값 삽입 

위의 그림과 같이 3배 확장시킨 lock 그래프에 주어진 lock 을 넣어주려고 한다. 

 

## 2. key 그래프의 탐색 위치 

우리가 생성한 lock 그래프 위에서 key 그래프가 이동 및 회전을 하면서 풀 수 있는지 확인을 하려고 한다. 

그때 탐색 처음의 시작 위치는 아래 그림과 같이 0,0이 될 것이다.  

 

탐색 마지막의 시작 위치는 어떻게 될까? 

(3*n, 3*n)이라고 이야기를 한다면, 손을 들어 자신의 머리를 내리치자 

아래 그림과 같이 (2*n, 2*n)이 될 것이다. 

 

위 그림을 표현하는 것이 아래 반복문이 된다. 

 

그럼 i <= n*2 이어야 되는 거 아닌가 의문이 든다면 맞다 !

하지만, 저긴 누가봐도 key가 lock을 못 푸는 곳 아닌가 ? 그래서 i, j 한쪽식 줄여서 lock 그래프의 마지막 위치까지를 탐색하게 했다. 

 

## 3. 이동 및 회전 

만약 아래 그림과 같이 key 가 저쪽을 탐색하고 있을 때, 

- 해당 부분에서 풀 수 있는 지 확인하고 

- 90도 한번 회전해서 lock을 풀 수 있는지 확인하고 

- 90도 한번 회전해서 lock을 풀 수 있는지 확인하고 

- 90도 한번 회전해서 lock을 풀 수 있는지 확인할 것이다. 

 

이 부분에 대한 코드가 이해가 가길 바란다. 

이곳에 필요한 함수가 세가지가 필요해지는데 아래와 같다. 

- locate 함수 : 현재 정 위치 key 그래프  

- rotate 함수 : 90도 회전시킨 key 그래프

- check 함수 : key와 lock 그래프를 비교해서 풀 수 있는지 확인하는 그래프 

 

즉, 이동 혹은 회전한 key 그래프를 생성하고, 계속 lock 그래프랑 비교하는 것이다. 

만약 풀 수 있다면 즉시 return true 이고, 

모든 탐색을 끝냈다면 return false를 하면된다. 

## 4. locate 함수 

이 함수는 현재 탐색의 시작위치를 매개변수로 받는다. 

그리고 key 그래프를 생성해주는 것인데, 

이해가 갈까? 

- key_graph를 생성해준다. (아까 lock_graph를 생성해준 것 같이 가로 세로 3배씩)

- 모든 값을 -1로 채운 뒤, 

- 기존의 key 값을 우리가 새롭게 생성한 key_graph에 넣어주는 것이다. 

 

아래 그림을 보면 확실히 이해가 가겠다 ! 

 

코드는 아래와 같다. 

## 5. rotate 함수 

자 이제 집중을 해야 한다. 난 좀 재밌게 구현했는데(이미 흔한 방법일지도? ),

이부분을 다른 분들은 어떻게 구현했는지 궁금하다. 

(이 블로그 글을 작성하고 구경 갈 예정.. )

 

아래 그림과 같이 우리의 key_graph를 아래서부터 탐색할 것이다. 

그리고 해당 좌표값이 -1 값이 아닐 때 배열에다가 계속 값을 저장할 것이다. 

 

그러다 보면, 아래 그림과 같이 저 값이 있는 순간들을 만나게되고, 저 순서대로 배열에 저장을 한다

그렇게 되면, 아래와 같은 2차원 배열이 생성된다. 

[[0,1,0]

[1,0,0]

[1,0,0]]

 

이 배열을 temp 배열이라고 했을 때, 

우리가 원래 가지고 있던 key_graph에 temp 배열을 순서대로 값을 넣어주면된다. 

 

그럼 아래 그림과 같이 회전한 그래프가 나오고 

이를 return 하면된다. 

 

이를 코드로 구현하면 아래와 같다. 

## 6. check 함수 

자, 이제는 key 그래프랑, lock 그래프를 비교하는 함수이다. 

우리는 어디만 보면 되는가? 

저 보라색 부분만 이제 값을 비교하면 된다. !! 

 

이때 세가지 경우에는 바로 lock을 풀지 못한다고 false를 return 하면 된다. 

- lock이 0인데, key가 -1인 경우  : 채워줘야 하는데 key의 돌기가 없음. 

- lock이 1인데, key가 1인 경우 : lock이 볼록 튀어나온 부분에, key도 볼록 튀어나옴. 

- lock이 0인데, key가 0인 경우 : 채워줘야 하는데 key의 돌기가 없음. 

 

짠 이렇게 되면 정답이라고 뜬다. 

근데, 이거 시험장에서 풀기 쉽지 않을 것 같다. 

왜냐하면 test case가 1개 뿐이라, 

내가 어떤 조건을 하나만 빼놔도 틀린 거니까,,, 

그자리에서 푼 분들 respect 합니다 

 

정답 코드 

function solution(key, lock) {
    let n = lock.length; 
    let m = key.length
    const lock_graph = Array.from({length:n*3}).map(() => new Array(n*3).fill(-1))
    //lock 그래프 채우기 
    for(let i=0; i<n; i++){
        for(let j=0; j<n; j++){
            lock_graph[i+n][j+n] = lock[i][j]
        }
    }

   //key 의 시작점 [i][j] 
    for(let i=0; i<n*2; i++){
        for(let j=0; j<n*2; j++){
           let temp_graph = locate(i, j)   
           let result = check(temp_graph, lock_graph)
           if(result) return true; 
           let rotate1_graph = rotate(temp_graph,i,j,n)
           let result1 = check(rotate1_graph, lock_graph)
           if(result1) return true; 
           let rotate2_graph = rotate(rotate1_graph,i,j,n)
           let result2 =check(rotate2_graph, lock_graph)
           if(result2) return true; 
           let rotate3_graph = rotate(rotate2_graph,i,j,n)
           let result3 =check(rotate3_graph, lock_graph)
           if(result3) return true; 
        }
    }
    return false; 
    //시작위치 받아서 key 그래프 채우고 return 
    function locate(x, y){
    const key_graph = Array.from({length:n*3}).map(() => new Array(n*3).fill(-1))
        for(let i=0; i<key.length; i++){
            for(let j=0; j<key.length; j++){
                key_graph[i+x][j+y] = key[i][j]
            }
        }
        return key_graph
    }
    //key 해당 좌표 받고 이걸 회전시켜 ... 90ㄷㅗ,,,
    //key의 시작 위치도 받기, key 길이도 받기 
    function rotate(graph, x, y, n){                  
       let temp = []; 
        for(let j=0; j<n*3; j++){
            let ver = []; 
           for(let i=n*3-1; i>=0; i--){
               if(graph[i][j] !== -1) ver.push(graph[i][j])
           }
           if(ver.length !== 0) temp.push(ver)
       }

        for(let i=0; i<temp.length; i++){
            for(let j=0; j<temp.length; j++){
                graph[i+x][j+y] = temp[i][j]
            }
        }
        return graph
    }
    //key그래프랑 lock 그래프 받아서 true인지 false인지 반환값 
    function check(temp_graph, lock_graph){ 
        let cnt = 0; 
        for(let i=n; i<2*n; i++){
            for(let j=n; j<2*n; j++){
                if(lock_graph[i][j] === 0 && temp_graph[i][j] === -1) return false;           
                if(lock_graph[i][j] === 1 && temp_graph[i][j] === 1) return false; 
                if(lock_graph[i][j] === 0 && temp_graph[i][j] === 0) return false;  
            }
        }
            return true; 
    }
}