2020 KAKAO BLIND RECRUITMENT : 자물쇠와 열쇠

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

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

 

# 접근법

0	0	0
1	0	0
0	1	1 / 1	1	1
		1	1	0
		1	0	1

1) 위와 같이 한쪽 귀퉁이만 겹치도록하는 사이즈의 큰 2차원 배열을 만든다.

 

2) 1행 1열 부터 시작하여 열 -> 행 모두 비교한다. 단 비교할 때 key의 값과 lock의 값을 더했을 때 합이 1이 아닌 0이나 2가 나오면 더 일치하지 않다는 의미이므로 더이상 비교하지 않는다.

 

3) 행과 열을 모두 순회 하였을 때에도 일치하는 값이 존재 하지 않는다면, 방향을 90도 회전 시켜준다.

이때 네 방향을 모두 해줘야 한다. 4번 반복한다.

 

4) 이렇게 비교하면서 만약 일치하는 (해당 위치의 key의 값과 lock의 값이 1일 경우) 경우 True를 반환하며 종료한다.

 

// 코드

class Solution {
    // 자물쇠가 열리는지 체크
    public boolean check(int startRow, int startCol, int[][] key, int[][] lock, int expandSize, int start, int end) {
        
        int[][] expandList = new int[expandSize][expandSize];
        // expandList에 key추가
        for(int row=0; row<key.length; row++) 
            for(int col=0; col<key.length; col++) 
                expandList[startRow + row][startCol + col] += key[row][col];           
        
        // expandList에 lock추가하면서 기존값이랑 더하기
        for(int row=start; row<=end; row++) {
            for(int col=start; col<=end; col++) {
                expandList[row][col] += lock[row-start][col-start];
                if(expandList[row][col] != 1) return false;
            }
        }
        
        return true;
    }
    
    // 키를 90도 회전시킨다.
    public int[][] rotation(int[][] key) {
        int keyLength = key.length;
        int[][] resKey = new int[keyLength][keyLength];
        
        for(int row=0; row<keyLength; row++) 
            for(int col=0; col<keyLength; col++)
                resKey[col][keyLength - 1 - row] = key[row][col];
        
        return resKey;
    }
    
    // main
    public boolean solution(int[][] key, int[][] lock) {
        // expandList에서 lock의 시작점        
        int start = key.length - 1;
        // expandList에서 lock의 끝점
        int end = lock.length + start - 1;
        // expandList 배열의 크기
        int expandSize = lock.length + (start * 2); 
        
        // 90도 방향으로 모든 부분을 체크해야므로 4번 반복한다.
        for(int i=0; i<4; i++) { 
            
            // 완탐을 시작한다.
            for(int row=0; row<=end; row++) {
                for(int col=0; col<=end; col++) {
                    // 자물쇠가 열리는지 체크한다.
                    if(check(row, col, key, lock, expandSize, start, end)) return true;
                }
            }
            
            // 만약 종료되지 않았다면 key의 방향을 90도 회전시켜준다.
            key=rotation(key);
        }        
 
        return false;
    }
}