[프로그래머스/Level3] 자물쇠와 열쇠 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• 브루트포스 (구현)

1. lock의 범위를 확장하고, 확장한 배열에  lock에 대한 정보를 입력한다.

  - Why? 키의 일부가 자물쇠 영역을 벗어나더라도, 키로 자물쇠를 열 수 있으면 정답이 되기 때문.

  - 그러므로 lock과 key가 겹칠 수 있는 모든 경우를 계산할 수 있을만큼 확장해야 한다.

  - 🔔 key의 크기와 lock의 크기가 항상 같진 않다!

 

  - 열쇠 이동거리 = 열쇠와 자물쇠가 처음 겹치는 부분 + 자물쇠의 크기

     ⇒ 확장한 배열 : 자물쇠 크기 + (열쇠 크기 -1) * 2

 

2. key를 시계 방향으로 총 4번 회전한다.

  - 회전하지 않은 경우, key 값을 그대로 newLock에 더한다. (∵ 자물쇠 0 + 홈 1 = 딱 맞음 1)

  - 90도 회전한 경우,   newLock[x + i][y + j] += key[j][len - i - 1];

  - 180도 회전한 경우, newLock[x + i][y + j] += key[len - i - 1][len- j - 1];

  - 270도 회전한 경우, newLock[x + i][y + j] += key[len - j - 1][i];

 

 

3. 회전한 key와 확장된 lock이 맞는지 확인한다.

  - newLock의 자물쇠 부분이 모두 1인지 확인하면 된다.

 

 

🔺 코드

class Solution {
    public boolean solution(int[][] key, int[][] lock) {
        
        // 1. lock을 확장한다.
        int point = key.length - 1;
        
        for(int x = 0 ; x < point + lock.length ; x++) {
            for(int y = 0 ; y < point + lock.length ; y++) {
                
                // 2. key를 시계 방향으로 회전하기
                for(int d = 0 ; d < 4 ; d++) {
                    
                    // newLock : 확장한 lock 배열
                    int[][] newLock = new int[lock.length + key.length * 2][lock.length + key.length * 2];
                    
                    // newLock에 lock에 대한 정보 입력하기
                    for(int i = 0 ; i < lock.length ; i++) {
                        for(int j = 0 ; j < lock.length ; j++)
                            newLock[i+point][j+point] = lock[i][j]; // 확장할 lock 배열 초기화
                    }
                    
                    // newLock 배열에 key 배열 더하기
                    match(newLock, key, d, x, y);
                    
                    // 3. key와 lock이 맞는지 확인하기
                    if(chk(newLock, point, lock.length))
                        return true;
                }
            }
        }
        
        return false;
    }
    
    public void match(int[][] newLock, int[][] key, int rot, int x, int y) {
        int len = key.length;
        
        for(int i = 0 ; i < len ; i++) {
            for(int j = 0 ; j < len ; j++) {
                if(rot == 0)        // 1) 회전하지 않은 경우, 그대로 newLock에 더하기
                    newLock[x+i][y+j] += key[i][j];
                else if(rot == 1)   // 2) 시계 방향으로 90도 회전한 경우
                    newLock[x+i][y+j] += key[j][len-i-1];
                else if(rot == 2)   // 3) 시계 방향으로 180도 회전한 경우
                    newLock[x+i][y+j] += key[len-i-1][len-j-1];
                else                // 4) 시계 방향으로 270도 회전한 경우 == 반시계 방향으로 90도 회전한 경우
                    newLock[x+i][y+j] += key[len-j-1][i];
            }
        }
    }
    
    public boolean chk(int[][] newLock, int point, int len) {
        for(int i = 0 ; i < len ; i++) {
            for(int j = 0 ; j < len ; j++) {
                if(newLock[point + i][point + j] != 1)
                    return false;
            }
        }
        return true;
    }
}

 

 

➕ 다른 풀이 방식

 

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

---

💦 어려웠던 점

- 해결 아이디어를 생각하는 것이 어려웠다.. 뭔가 숫자 범위가 작아서 브루트포스라는 감은 잡았는데 그 이후는 감감무소식,,,

 

 

🧐 새로 알게 된 내용

- 배열을 확장해서 조건과 일치하는지 일일이 확인하는 아이디어

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 최고의 설명..

[프로그래머스]자물쇠와 열쇠 - JAVA