[Java] 프로그래머스 - 자물쇠와 열쇠 (3단계)

코딩 테스트 풀이 체크리스트
2시간 내에 풀었는가?	O
본인의 실력으로 풀었는가?	O

 

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

 

 

 

 

 

import java.util.*;
class Solution {
    Point[][] points;
    int[][] table;
    int n, m;
    boolean answer;
    public boolean solution(int[][] key, int[][] lock) {
        answer = false;
        n = key.length;
        m = lock.length;
        table = new int[m + (n-1)*2][m + (n-1)*2];
        
        int spin = 0;
        int start = n-1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (key[i][j] == 1) spin++;
            }
        }
        
        //돌기가 있는 점들 0도, 90도, 180도, 270도 버전으로 미리 배열에 담아놓기
        points = new Point[4][spin];
        int position = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (key[i][j] == 1) {
                    points[0][position] = new Point(i, j);
                    points[1][position] = new Point(j, n-i-1);
                    points[2][position] = new Point(n-i-1, n-j-1);
                    points[3][position] = new Point(n-j-1, i);
                    position++;
                }
            }
        }
        
        //table은 key가 상하좌우 대각선 모두 다 넣을 수 있도록 범위를 넓힌 상태에서
        //lock 부분 체크해놓기
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                table[i+n-1][j+n-1] = lock[i][j];
            }
        }
        
        //key 넣으면서 체크하기
        for (int i = 0; i < table.length - (n-1); i++) {
            for (int j = 0; j < table.length - (n-1); j++) {
                for (int k = 0; k < 4; k++) {
                    if (call(i, j, k)) return true;
                }
            }
        }
        
        return false;
    }
    
    //만약 func함수 호출 후 answer이 true가 된다면 그냥 바로 리턴하기
    public boolean call(int x, int y, int index) {
        func(x, y, n-1, index, 0);
        if (answer) return true;
        
        return false;
    }
    
    public void func(int sX, int sY, int sLock, int index, int num) {
    	//num과 points[index]의 길이가 같으면 key의 돌기를 다 돈 것이기 때문에
        //lock 부분이 전부 1이면 true 아니면 false 리턴
        if (num == points[index].length) {
            for (int i = sLock; i < sLock+m; i++) {
                for (int j = sLock; j < sLock+m; j++) {
                    if (table[i][j] == 0 || table[i][j] == 2) return;
                }
            }
            
            answer = true;
            return;
        }
        
        Point p = points[index][num];
        
        if (table[sX + p.x][sY + p.y] == 0) {
            table[sX + p.x][sY + p.y]++;
            func(sX, sY, sLock, index, num+1);
            table[sX + p.x][sY + p.y]--;
        }
        
    }
}

class Point {
    int x, y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

 

테스트 1 〉	통과 (0.22ms, 75.7MB)
테스트 2 〉	통과 (0.19ms, 76.3MB)
테스트 3 〉	통과 (1.07ms, 81.6MB)
테스트 4 〉	통과 (0.18ms, 73.2MB)
테스트 5 〉	통과 (0.55ms, 73.7MB)
테스트 6 〉	통과 (0.47ms, 76.5MB)
테스트 7 〉	통과 (1.08ms, 73.8MB)
테스트 8 〉	통과 (2.12ms, 76.1MB)
테스트 9 〉	통과 (1.27ms, 79.5MB)
테스트 10 〉	통과 (2.19ms, 72.5MB)
테스트 11 〉	통과 (3.20ms, 71.9MB)
테스트 12 〉	통과 (0.19ms, 79.4MB)
테스트 13 〉	통과 (0.75ms, 75.2MB)
테스트 14 〉	통과 (0.33ms, 77.6MB)
테스트 15 〉	통과 (1.02ms, 73.8MB)
테스트 16 〉	통과 (0.83ms, 79.1MB)
테스트 17 〉	통과 (0.68ms, 83.8MB)
테스트 18 〉	통과 (0.80ms, 79MB)
테스트 19 〉	통과 (0.19ms, 77.7MB)
테스트 20 〉	통과 (1.15ms, 70.5MB)
테스트 21 〉	통과 (1.30ms, 73.1MB)
테스트 22 〉	통과 (0.83ms, 78.8MB)
테스트 23 〉	통과 (0.46ms, 74.2MB)
테스트 24 〉	통과 (0.40ms, 75.1MB)
테스트 25 〉	통과 (1.22ms, 75.4MB)
테스트 26 〉	통과 (3.86ms, 73.3MB)
테스트 27 〉	통과 (3.33ms, 76.9MB)
테스트 28 〉	통과 (0.81ms, 76.2MB)
테스트 29 〉	통과 (0.51ms, 72.6MB)
테스트 30 〉	통과 (0.93ms, 78.3MB)
테스트 31 〉	통과 (1.23ms, 77.3MB)
테스트 32 〉	통과 (1.61ms, 79.4MB)
테스트 33 〉	통과 (0.99ms, 75.8MB)
테스트 34 〉	통과 (0.30ms, 73.7MB)
테스트 35 〉	통과 (0.37ms, 71.1MB)
테스트 36 〉	통과 (0.40ms, 75.7MB)
테스트 37 〉	통과 (0.38ms, 77.7MB)
테스트 38 〉	통과 (0.28ms, 77.5MB)