[CLOCKSYNC] Synchronizing Clocks
Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.
문제 : https://www.algospot.com/judge/problem/read/CLOCKSYNC
algospot.com :: CLOCKSYNC
Synchronizing Clocks 문제 정보 문제 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록
www.algospot.com
이 문제를 풀 수 있는 방법은 2가지가 있습니다.
각각의 방법에 대해 알아보도록 하겠습니다. 🤔
1. 재귀를 이용한 완전탐색
각각의 시계를 0~3회씩 돌려, 가장 적은 수로 시계를 맞춘 경우의 수를 찾습니다.
4회 이상부터는 0회와 동일하기 때문에 해당 경우의 수는 찾지 않습니다.
|
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
|
import java.util.*;
public class Main {
private static final int IMPOSSIBLE = -1;
private static final int MAX_USE_COUNT = 4;
private static final int[][] controllers = new int[][] {
{0, 1, 2},
{3, 7, 9, 11},
{4, 10, 14, 15},
{0, 4, 5, 6, 7},
{6, 7, 8, 10, 12},
{0, 2, 14, 15},
{3, 14, 15},
{4, 5, 7, 14, 15},
{1, 2, 3, 4, 5},
{3, 4, 5, 9, 13}
};
public static void main(String[] args) {
int[] states = new int[16];
Scanner scanner = new Scanner(System.in);
int cases = scanner.nextInt();
while (cases-- > 0) {
for (int i = 0; i < 16; ++i) {
states[i] = scanner.nextInt() % 12;
}
System.out.println(getMinTimes(states, 0, 0));
}
}
private static int getMinTimes(int[] states, int index, int times) {
if (isComplete(states)) return times;
if (index >= controllers.length) return IMPOSSIBLE;
int[] controller = controllers[index];
int ret = IMPOSSIBLE;
for (int i = 0; i < MAX_USE_COUNT; ++i) {
int candidate = getMinTimes(states, index + 1, times + i);
if (ret == IMPOSSIBLE) ret = candidate;
else if (candidate != IMPOSSIBLE) ret = Math.min(ret, candidate);
for (int controlIndex : controller) states[controlIndex] = (states[controlIndex] + 3) % 12;
}
return ret;
}
private static boolean isComplete(int[] states) {
for (int state : states) if (state != 0) return false;
return true;
}
}
|
cs |
2. 문제 속 힌트 사용
각 시계에 대해 조정할 수 있는 버튼을 나열해보면, 다음과 같습니다.
0 : 0, 3, 5
1 : 0, 8
2 : 0, 5, 8
3 : 1, 6, 8, 9
4 : 2, 3, 7, 8, 9
5 : 3, 7, 8, 9
6 : 3, 4
7 : 1, 3, 4, 7
8 : 4,
9 : 1, 9
10 : 2, 4
11 : 1
12 : 4
13 : 9
14 : 2, 5, 6, 7
15 : 2, 5, 6, 7
주의깊게 살펴봐야할 부분은 시계를 조정하기 위해 사용할 수 있는 버튼이 오직 1개만 존재하는 경우가 존재하는 것을 확인해볼 수 있습니다.
(11번째 시계는 오직 1번 버튼으로만 조정 가능)
이와 같은 경우에 해당하는 시계부터 하나씩 조정하는 것을 고려하면, 다음의 순서를 나열해볼 수 있습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
private static final int[][] controllerAndBiasClockOrders = new int[][]{
{1, 11},
{4, 8},
{9, 9},
{2, 10},
{3, 6},
{7, 7},
{8, 4},
{0, 1},
{5, 2},
{3, 0},
{6, 3}
}
|
cs |
위의 배열을 이용하여 1번 버튼을 11번 시계가 먼저 12시가 되도록, 4번 버튼을 8번 시계가 12시가 되도록, 9번 버튼을 9번 시계가 12시가 되도록...... 조정하도록 합니다.
이를 이용한 코드는 다음과 같습니다. 😆
|
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
|
import java.util.*;
public class Main {
private static final int IMPOSSIBLE = -1;
private static final int MAX_USE_COUNT = 4;
private static final int[][] controllers = new int[][] {
{0, 1, 2},
{3, 7, 9, 11},
{4, 10, 14, 15},
{0, 4, 5, 6, 7},
{6, 7, 8, 10, 12},
{0, 2, 14, 15},
{3, 14, 15},
{4, 5, 7, 14, 15},
{1, 2, 3, 4, 5},
{3, 4, 5, 9, 13}
};
public static void main(String[] args) {
int[] states = new int[16];
Scanner scanner = new Scanner(System.in);
int cases = scanner.nextInt();
while (cases-- > 0) {
for (int i = 0; i < 16; ++i) {
states[i] = scanner.nextInt() % 12;
}
System.out.println(getMinTimes(states, 0, 0));
}
}
private static int getMinTimes(int[] states, int index, int times) {
if (isComplete(states)) return times;
if (index >= controllers.length) return IMPOSSIBLE;
int[] controller = controllers[index];
int ret = IMPOSSIBLE;
for (int i = 0; i < MAX_USE_COUNT; ++i) {
int candidate = getMinTimes(states, index + 1, times + i);
if (ret == IMPOSSIBLE) ret = candidate;
else if (candidate != IMPOSSIBLE) ret = Math.min(ret, candidate);
for (int controlIndex : controller) states[controlIndex] = (states[controlIndex] + 3) % 12;
}
return ret;
}
private static boolean isComplete(int[] states) {
for (int state : states) if (state != 0) return false;
return true;
}
}
|
cs |
이 방법은 완전 탐색하는 방법이 아닌, 문제의 힌트를 이용해 특정 방법으로만 찾아 처리하기 때문에 속도가 더 빠를 수 있음을 볼 수 있습니다. (4^10회 vs 10 회)
처음에는 시간제한이 10,000 ms 이기 때문에 완전탐색으로 충분히 풀 수 있을 것이라 생각하고 접근을 하게 되었습니다.
그런데 다른 사람들의 처리 시간이 완전 탐색을 했을 때의 시간보다 너무 짧게 나오는 것을 확인하고 다른 방법을 찾아보다 이와 같은 힌트가 있음을 알게되었습니다.
한번 두 가지 방법을 모두 살펴보는 것을 추천드립니다.
이 포스트를 읽어주셔서 감사합니다. 🙇🏻♂️
'개발이야기 > 알고스팟' 카테고리의 다른 글
| [SHISENSHO] Shisen-sho (0) | 2022.01.03 |
|---|---|
| [WEEKLYCALENDAR] Weekly Calendar (0) | 2022.01.03 |
| [HAMMINGCODE] Hamming Code (0) | 2021.12.30 |
| [WEIRD] Weird Numbers (0) | 2021.12.30 |
| [XHAENEUNG] 째능 교육 (0) | 2021.12.29 |