[CLOCKSYNC] Synchronizing Clocks

Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

문제 : https://www.algospot.com/judge/problem/read/CLOCKSYNC

algospot.com ::   CLOCKSYNC

이 문제를 풀 수 있는 방법은 2가지가 있습니다.
각각의 방법에 대해 알아보도록 하겠습니다. 🤔

 

 

1. 재귀를 이용한 완전탐색

 

각각의 시계를 0~3회씩 돌려, 가장 적은 수로 시계를 맞춘 경우의 수를 찾습니다.
4회 이상부터는 0회와 동일하기 때문에 해당 경우의 수는 찾지 않습니다.

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;
    }
}

 

 

 

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번 버튼으로만 조정 가능)

이와 같은 경우에 해당하는 시계부터 하나씩 조정하는 것을 고려하면, 다음의 순서를 나열해볼 수 있습니다.

 

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}
}

 

위의 배열을 이용하여 1번 버튼을 11번 시계가 먼저 12시가 되도록, 4번 버튼을 8번 시계가 12시가 되도록, 9번 버튼을 9번 시계가 12시가 되도록...... 조정하도록 합니다.

이를 이용한 코드는 다음과 같습니다. 😆

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;
    }
}

이 방법은 완전 탐색하는 방법이 아닌, 문제의 힌트를 이용해 특정 방법으로만 찾아 처리하기 때문에 속도가 더 빠를 수 있음을 볼 수 있습니다. (4^10회 vs 10 회)
처음에는 시간제한이 10,000 ms 이기 때문에 완전탐색으로 충분히 풀 수 있을 것이라 생각하고 접근을 하게 되었습니다.
그런데 다른 사람들의 처리 시간이 완전 탐색을 했을 때의 시간보다 너무 짧게 나오는 것을 확인하고 다른 방법을 찾아보다 이와 같은 힌트가 있음을 알게되었습니다.

한번 두 가지 방법을 모두 살펴보는 것을 추천드립니다.
이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️