자물쇠와 열쇠
문제정의
열쇠의 돌기부분이 자물쇠의 홈에 맞는지 판별하는 문제이다. 열쇠를 자물쇠에 맞출 때, 열쇠가 자물쇠 바깥으로 삐져나올 수 있다. 하지만 자물쇠와 열쇠의 돌기부분이 서로 맞물리면 안된다. 자세한 사항은 아래 링크에서 확인하길 바란다.
문제 링크
문제풀이
전체 코드는 다음과 같다. 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
91import 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번 과정 코드부터 살펴보자 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
}
}
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;
}
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(m^2n^2)\)이다.
테스트
처음으로 2시간 안에 level3문제를 스스로 풀어서 기쁘다. 멘탈만 흔들리지 않으면 성장할 수 있다고 생각하는 오늘이다. 요새 네카라쿠배 2차테스트를 하는데 알고보니 실수를 해서 점수를 다 날려 먹게 생겼다 하... 2일차까지 테스트 점수가 다 꽝인데 그래도 포기하지 않고 끝까지 해보기로 했다. 학원의 힘을 빌리지 않고도 성장할 수 있으니까! 가벼운 마음으로 테스트에 임하자.