알고리즘) 카카오 블라인드 채용 2020, 자물쇠와 열쇠

Kakao Blind Recruitment 2020

문자열 압축

프로그래머스

 

풀이

처음에는 DFS로 해야하나 고민하다가, 열쇠가 회전하는 경우(+4) 열쇠의 이동 범위 등을 생각하면 시간초과가 분명할 것 같아서 포기했다. 오래 고민하다가 감이 안잡혀서 다른 분들의 로직을 참고했는데, 자물쇠의 크기를 3배 확장하는 방법이 존재했다.. 생각보다 간단한 문제여서 크게 반성했다.. 어렵게만 접근한 것 같았다.. 이후 로직은 스스로 생각했다.

 

1. 자물쇠의 크기를 3배 확장하고, 원래 자물쇠의 정보를 확장한 배열의 정중앙에 둔다.

2. 열쇠를 0도, 90도, 180도, 270도 돌린 정보를 저장한다. (0도 == 360도)

3. 확장된 자물쇠를 돌면서 열쇠를 맞춰본다.

 3-1. lockY=1+(newLock.length/3-key.length) <- 이 부분은 확장된 자물쇠를 도는 for문의 시작 부분인데, 자물쇠의 좌측 상단 부분이 열쇠의 우측 하단에 닿게 하기 위한 설정이다. 그 이전의 범위는 검사 하나마나 필요가 없으므로 조금이라도 줄여주기 위해 설정했다.

 3-2. 자물쇠가 확장된 부분인지 원래 부분인지 판단하여, 원래 자물쇠인 부분에서만 로직이 돌아가게 한다.

 3-3. 자물쇠와 열쇠의 돌기 부분끼리 만난다면, 문제 조건에 따라 break 해줬다.

 3-4. 또한, 자물쇠의 홈 부분에 열쇠 또한 홈이라면 열 수 없어서 break 해줬다.

 3-5. 자물쇠의 홈 부분에 열쇠의 돌기가 들어간 경우 count해줘서, 검사가 끝난 후 count와 열쇠가 맞을 수 있는 홈의 개수를 비교해 return해줬다.

 

코드

import java.util.ArrayList;

public class LockNKey_2019 {

    private static boolean solution(int[][] key, int[][] lock) {
        boolean answer = false;

        int[][] newLock = getNewLock(lock);
        ArrayList<int[][]> keyList = getKeyList(key);
        int hole = getHole(lock);
        for(int i=0; i<4; i++) {
            if(checkUnlock(keyList.get(i), newLock,hole)) {
                answer = true;
                break;
            }
        }

        return answer;
    }

    private static int getHole(int[][] lock) {
        int cnt =0;
        for(int[] line : lock) {
            for(int num : line) {
                if(num ==0) {
                    cnt++;
                }
            }
        }
        return cnt;
    }

    private static int[][] getNewLock(int[][] lock) {
        int len = lock.length;
        int[][] result = new int[len*3][len*3];
        for(int y=len; y<len*2; y++) {
            for(int x=len; x<len*2; x++) {
                result[y][x] = lock[y-len][x-len];
            }
        }
        return result;
    }

    private static ArrayList<int[][]> getKeyList(int[][] key) {
        ArrayList<int[][]> result = new ArrayList<>();
        result.add(key);
        for(int i=0; i<3; i++) {
            result.add(getRotateKey(result.get(i)));
        }
        return result;
    }

    private static int[][] getRotateKey(int[][] key) {
        int len = key.length;
        int[][] result = new int[len][len];

        for(int y=0; y<len; y++) {  // rotate right
            for(int x=0; x<len; x++) {
                result[x][len-1-y] = key[y][x];
            }
        }

        return result;
    }

    private static boolean checkUnlock(int[][] key, int[][] newLock, int hole) {
        for(int lockY=1+(newLock.length/3-key.length); lockY<newLock.length/3*2; lockY++) {
            for(int lockX=1+(newLock.length/3-key.length); lockX<newLock.length/3*2; lockX++) {
                //좌표를 돌면서 키 확인
                int cnt =0;
                boolean isBreak = false;
                for(int keyY=0; keyY<key.length; keyY++) {
                    for(int keyX=0; keyX<key.length; keyX++) {
                        int mapY = lockY + keyY;
                        int mapX = lockX + keyX;
                        if(isOriginalSpot(mapY, mapX, newLock.length)) {
                            if(newLock[mapY][mapX] ==1) {   // 자물쇠의 홈
                                if(key[keyY][keyX] == 1) {  // 서로 돌기면
                                    isBreak = true;
                                    break;
                                }
                            } else {    // 열쇠 돌기가 들어와야 하는 부분
                                if(key[keyY][keyX] ==0) { // 돌기가 없으면 못연다
                                    isBreak = true;
                                    break;
                                }
                                cnt++;
                            }
                        }
                    }
                    if(isBreak) {
                        break;
                    }
                }
                if(cnt == hole) {
                    return true;
                }
            }
        }

        return false;
    }

    private static boolean isOriginalSpot(int y, int x, int length) {
        int originLen = length/3;
        if(x >= originLen && x <originLen*2 && y >=originLen && y < originLen*2) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] key = {{0, 0, 0}, {1, 0, 0}, {0, 1, 1}};
        int[][] lock = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}};

        boolean result = solution(key,lock);

        if(result) {
            System.out.println("푼다");
        } else {
            System.out.println("못푼다");
        }
    }
 }