[프로그래머스] 자물쇠와 열쇠(Python, Java)

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

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

문제 설명

고고학자인 튜브는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다.

잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.

자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.

열쇠를 나타내는 2차원 배열 key와 자물쇠를 나타내는 2차원 배열 lock이 매개변수로 주어질 때, 열쇠로 자물쇠를 열수 있으면 true를, 열 수 없으면 false를 return 하도록 solution 함수를 완성해주세요.

제한사항

• key는 M x M(3 ≤ M ≤ 20, M은 자연수)크기 2차원 배열입니다.
• lock은 N x N(3 ≤ N ≤ 20, N은 자연수)크기 2차원 배열입니다.
• M은 항상 N 이하입니다.
• key와 lock의 원소는 0 또는 1로 이루어져 있습니다.
  • 0은 홈 부분, 1은 돌기 부분을 나타냅니다.

입출력 예

key	lock	result
[[0, 0, 0], [1, 0, 0], [0, 1, 1]]	[[1, 1, 1], [1, 1, 0], [1, 0, 1]]	true

입출력 예에 대한 설명

key를 시계 방향으로 90도 회전하고, 오른쪽으로 한 칸, 아래로 한 칸 이동하면 lock의 홈 부분을 정확히 모두 채울 수 있습니다.

풀이 설명

1. lock이 전부 1로 되어있으면 홈이 없는 것이므로 무조건 열린다.

2. 아래 그림처럼 lock의 사방으로 (lock의 길이 - 1) 만큼 확장한 배열 extendList를 만들고, 확장한 부분은 0으로 채운다.

   (이렇게 하면 key를 이용해 extendList를 탐색할 때 편리하다.)

3. extendLlist에서 lock이 시작하고 끝나는 인덱스 start, end를 구한다.

   start = lock의 길이 - 1

   end = start + lock의 길이

0	0	0	0	0	0	0
0	0	0	0	0	0	0
0	0	1	1	1	0	0
0	0	1	1	0	0	0
0	0	1	0	1	0	0
0	0	0	0	0	0	0
0	0	0	0	0	0	0

4. key를 모든 방향에서 맞춰볼 것이므로 4번 반복

5. key를 lock에 한 칸씩 위에서 아래로 움직이므로 총 움직일 횟수와 같은 end만큼 반복

6. key가 한 행에 있을 때 한 칸씩 왼쪽에서 오른쪽으로 움직이므로 총 움직일 횟수와 같은 end만큼 반복

7. extendList에서 key의 포지션이 잡히면 key의 모든 홈을 체크해야 하므로, key의 행 수만큼 반복

8. key의 각 행마다 열 수만큼 반복

  8-1. 만약 key와 extendList 모두 1이면 열리지 않으므로 breaker=true, break

  8-2. 만약 key와 extendList 모두 0이면, 해당 인덱스가 extendList의 lock 부분이 맞는지 체크 후, 아니면 breaker=true, break

  8-3. key가 1이고 extendList가 0이면, 해당 인덱스가 extendList의 lock 부분이 맞는지 체크 후, 맞으면 count + 1

9. 8번이 끝났을때 breaker가 true면 맞지 않았다는 뜻이므로, count를 0으로 초기화 후 break

10. 7번이 끝났을때 lock의 홈 개수와 count의 개수가 같다면, key로 lock을 열 수 있으므로, return true

11. 5번이 끝나면 key를 90도 회전하여 다시 체크

Python3 코드

def rotation(key, n):
    arr = []
    for i in range(n):
        a = []
        for j in range(n-1, -1, -1):
            a.append(key[j][i])
        arr.append(a)
    return arr

def solution(key, lock):
    keyLen = len(key)
    lockLen = len(lock)
    lockCnt = 0
    
    if lock.count([1] * lockLen) == lockLen: #홈이 없다면 무조건 열림
        return True
    
    extendList = [[0] * (lockLen * 3 - 2) for _ in range((lockLen * 3 - 2))]
    start = lockLen - 1
    end = start + lockLen
    for i in range(lockLen):
        for j in range(lockLen):
            extendList[i + start][j + start] = lock[i][j]
            if lock[i][j] == 0:
                lockCnt += 1
    
    for i in range(4):
        for a in range(end):
            for b in range(end):
                breaker = False
                count = 0
                #print('--------------------')
                for j in range(keyLen):
                    for k in range(keyLen):
                        #print('key',j,k,' extendList',j+a,k+b)
                        if key[j][k] == 1 and extendList[j + a][k + b] == 1:
                            breaker = True
                            break
                        elif key[j][k] == 0 and extendList[j + a][k + b] == 0:
                            if not start <= j + a < end:
                                continue
                            elif not start <= k + b < end:
                                continue
                            else:
                                breaker = True
                                break
                        elif key[j][k] == 1 and extendList[j + a][k + b] == 0:
                            if start <= j + a < end and start <= k + b < end:
                                count += 1
                    if breaker:
                        count = 0
                        break
                #print(count)
                if count == lockCnt:
                    return True
        key = rotation(key, keyLen)
        
    return False

Java 코드

import java.util.*;

class Solution {
    
    public int[][] rotation(int[][] arr, int len){
        int[][] newArr = new int[len][len];
        
        for(int i=0; i<len; i++){
            int[] addArr = new int[len];
            for(int j=0; j<len; j++){
                addArr[j] = arr[len-j-1][i];
            }
            newArr[i] = addArr;
        }
        
        return newArr;
    }
    
    public boolean solution(int[][] key, int[][] lock) {
        boolean answer = false;
        int keyLen = key.length;
        int lockLen = lock.length;
        int start = lockLen - 1; //extendList에서 lock부분의 시작인덱스
        int end = start + lockLen; //extendList에서 lock부분의 종료인덱스
        boolean breaker = false;
        int count = 0;
        int lockCnt = 0;
        
        int[][] extendList = new int[lockLen * 3 - 2][lockLen * 3 - 2];
        //////extendList, lockCnt 초기화/////
        for(int i=0; i<lockLen; i++){
            for(int j=0; j<lockLen; j++){
                extendList[i + start][j + start] = lock[i][j];
                if(lock[i][j] == 0) lockCnt++;
            }
        }
        
        //lock이 다 1일때 true 리턴
        if(lockCnt == 0) return true;
        
        for(int r=0; r<4; r++){
            for(int i=0; i<end; i++){
                for(int j=0; j<end; j++){
                    breaker = false;
                    count = 0;
                    for(int a=0; a<keyLen; a++){
                        for(int b=0; b<keyLen; b++){
                            if(key[a][b] == 1 && extendList[i + a][j + b] == 1){
                                breaker = true;
                                break;
                            }
                            //만약 둘다 0이면 lock 범위 내인지 확인
                            else if(key[a][b] == 0 && extendList[i + a][j + b] == 0){
                                if(start <= i + a && i + a < end && start <= j + b && j + b < end){
                                    breaker = true;
                                    break;
                                }
                            }
                            else if(key[a][b] == 1 && extendList[i + a][j + b] == 0){
                                if(start <= i + a && i + a < end && start <= j + b && j + b < end){
                                    count++;
                                }
                            }
                        }
                        if(breaker) break;
                        if(count == lockCnt) return true;
                    }
                }
            }
            if(count == lockCnt) return true;
            key = rotation(key, keyLen);
        }
        
        return answer;
    }
}