자물쇠와 열쇠

Posted on Edited on In , ,

문제정의

열쇠의 돌기부분이 자물쇠의 홈에 맞는지 판별하는 문제이다. 열쇠를 자물쇠에 맞출 때, 열쇠가 자물쇠 바깥으로 삐져나올 수 있다. 하지만 자물쇠와 열쇠의 돌기부분이 서로 맞물리면 안된다. 자세한 사항은 아래 링크에서 확인하길 바란다.

문제 링크

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
import java.util.Arrays;

public class LockandKey {

    //프로그래머스 문제풀이 level3 자물쇠와 열쇠
    public static void main(String[] args) {
        int[][] key = {
            {0,0,0},
            {0,0,0},
            {0,0,0}
        };
        int[][] lock = {
            {1,1,1},
            {1,1,0},
            {1,0,1}
        };

        boolean answer = false;

        //get rotation
        int[][][] keys = new int[4][key.length][key.length];
        //make keys
        for(int i = 0; i < key.length; i++)
        {
            for(int j = 0; j < key.length; j++)
            {
                keys[0][i][j] = key[i][j];
                keys[1][i][j] = key[key.length-1-j][i];
                keys[2][i][j] = key[key.length-1-i][key.length-1-j];
                keys[3][i][j] = key[j][key.length-1-i];
            }
        }
        //count zero
        int zero = 0;
        for(int i = 0; i < lock.length; i++)
        {
            for(int j = 0; j < lock.length; j++)
            {
                if(lock[i][j] == 0)
                    zero++;
            }
        }

        //find match key
        int m = key.length;
        int n = lock.length;
        for(int i = 0; i < 4; i++) //4keys
        {
            for(int c = 0; c < m+n-1; c++)
            {
                for(int r = 0; r < m+n-1; r++)//right corner position
                {
                    //check if key is matched
                    boolean match = true;
                    int zero_cnt = zero;
                    for(int y = c-m+1; y <= c; y++)
                    {
                        for(int x = r-m+1; x <= r; x++)
                        {
                            if(y < 0 || x < 0 || y >= lock.length || x >= lock.length)
                                continue;
                            int v = keys[i][y-(c-m+1)][x-(r-m+1)];
                            if(v == 1 && lock[y][x] == 1)
                            {
                                match = false;
                                break;
                            }
                            else if(v == 1 && lock[y][x] == 0)
                                zero_cnt--;
                        }
                        if(!match)
                            break;
                    }
                    //if answer found
                    if(zero_cnt == 0)
                    {
                        answer = true;
                        break;
                    }
                        
                }
                if(answer)
                    break;
            }
            if(answer)
                break;
        }
        System.out.println(answer);
    }
    
}
코드가 긴편이다. 전체적인 과정을 생각해보면 다음과 같다. 1. 열쇠는 회전이 가능하다 90도씩 회전한 4개 열쇠를 만든다. 2. 자물쇠에서 홈이 몇 개 있는지 센다. 3. 자물쇠에 각 열쇠를 끼워본다. 4. 자물쇠에 열쇠가 맞고 모든 홈을 채웠다면 답을 true로 한다. 5. 그렇지 않다면 다음 자리로 열쇠를 이동해본다.

1번 과정 코드부터 살펴보자 

1
2
3
4
5
6
7
8
9
10
11
12
13
//get rotation
int[][][] keys = new int[4][key.length][key.length];
//make keys
for(int i = 0; i < key.length; i++)
{
    for(int j = 0; j < key.length; j++)
    {
        keys[0][i][j] = key[i][j];
        keys[1][i][j] = key[key.length-1-j][i]; //90
        keys[2][i][j] = key[key.length-1-i][key.length-1-j]; //180
        keys[3][i][j] = key[j][key.length-1-i]; //270
    }
}
회전 각에 따라 총 4개의 열쇠가 나올 수 있다. 회전을 구현하는 방법은 읽는 순서를 달리하면 된다. 이는 코드에 나와있으니 코드를 스스로 공부하고 그림을 그려가면서 알아보길 바란다. 이렇게 하면 4개의 열쇠꾸러미를 손에 쥘 수 있다.

2번 과정은 2차원 배열을 순회하면서 0인 부분을 세면 된다. 이 부분은 간단하므로 넘어가자.

3,4,5과정은 한 코드로 나타나 있다. 범위 설정에 주의하면서 코드를 보자. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//find match key
int m = key.length;
int n = lock.length;
for(int i = 0; i < 4; i++) //4keys
{
    for(int c = 0; c < m+n-1; c++)
    {
        for(int r = 0; r < m+n-1; r++)//right corner position
        {
            //check if key is matched
            boolean match = true;
            int zero_cnt = zero;
            for(int y = c-m+1; y <= c; y++)
            {
                for(int x = r-m+1; x <= r; x++)
                {
                    if(y < 0 || x < 0 || y >= lock.length || x >= lock.length)
                        continue;
                    int v = keys[i][y-(c-m+1)][x-(r-m+1)];
                    if(v == 1 && lock[y][x] == 1)
                    {
                        match = false;
                        break;
                    }
                    else if(v == 1 && lock[y][x] == 0)
                        zero_cnt--;
                }
                if(!match)
                    break;
            }
            //if answer found
            if(zero_cnt == 0)
            {
                answer = true;
                break;
            }
                
        }
        if(answer)
            break;
    }
    if(answer)
        break;
}
첫번째 반복은 열쇠 꾸러미에서 몇 번째 열쇠를 쓸 것인지 나타낸다. 열쇠는 총 4개이므로 4개의 열쇠에 대해 각각 수행해본다.

c와 r의 반복은 열쇠를 이동해보는 반복이다. c와 r은 열쇠의 오른쪽 아래 모서리가 위치하는 점을 기준으로 하였다. 모든 경우의 수를 해보려면 오른쪽 아래 모서리가 (0,0)에서 (m+n-2, m+n-2)까지 움직여야 한다(m은 열쇠의 가로, n은 자물쇠의 가로이다).

열쇠를 이동했다면 이제 홈에 들어맞는지 확인해야 한다. 이는 y와 x에 대한 반복문으로 나타냈다. 오른쪽 아래 모서리를 기준으로 움직였기 때문에, 열쇠가 들어맞는지 검사하기 위해선 위쪽 모서리 값을 알아야 한다. 이는 (c-m+1, r-m+1)이다. 그럼 여기부터 열쇠와 자물쇠가 들어맞는지 확인하면 된다.

일단 x나 y가 자물쇠 범위 밖을 벗어났다면 비교할 필요가 없으므로 continue를 한다. 만약 범위 이내라면 둘을 비교한다. 이때 열쇠는 [0][0]부터 비교하는 것이기 때문에, 현재 y와 x에서 왼쪽 모서리 값을 빼준다.

만약 비교하는 열쇠와 자물쇠가 모두 돌기부분이라면 들어맞지 않으므로 break를 통해 탈출한다. 이 때 match를 이용해 한 번더 반복을 탈출하여 열쇠가 바로 이동할 수 있도록 한다.

만약 열쇠는 돌기이고 자물쇠가 홈부분이면, zero_cnt를 하나씩 줄인다. 모든 검사를 마칠 때 이 값이 0이라면 열쇠가 자물쇠에 들어맞다는 뜻이므로, 모든 반복을 탈출하고 답을 출력한다.

반복 횟수를 계산해보자면 (m+n−2)(m+n−2)m∗m이 된다. 따라서 최고차항을 따로 떼어내면 최종 시간복잡도는 O(m2n2)이다.

테스트



처음으로 2시간 안에 level3문제를 스스로 풀어서 기쁘다. 멘탈만 흔들리지 않으면 성장할 수 있다고 생각하는 오늘이다. 요새 네카라쿠배 2차테스트를 하는데 알고보니 실수를 해서 점수를 다 날려 먹게 생겼다 하... 2일차까지 테스트 점수가 다 꽝인데 그래도 포기하지 않고 끝까지 해보기로 했다. 학원의 힘을 빌리지 않고도 성장할 수 있으니까! 가벼운 마음으로 테스트에 임하자.