☌

[WEEKLYCALENDAR] Weekly Calendar

개발이야기/알고스팟2022. 1. 3. 14:14

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

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

 

algospot.com :: WEEKLYCALENDAR

Weekly Calendar 문제 정보 문제 당신은 오랜 기간 동안 어머니로부터의 잔소리, TV 혹은 자기 계발 서적 등에서 떠드는 진부한 소리에 세뇌된 끝에 오늘부터 성실히 살기로 결심했다. 그 첫 번째 단

www.algospot.com

 

풀이입니다. 🤔

 

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
import java.util.*;
 
public class Main {
    private static final String[] weekStrings = new String[]{
            "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"
    };
    private static final int[] endDayOfMonths = new int[]{
            31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
    };
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int cases = scanner.nextInt();
        while (cases-- > 0) {
            List<Integer> daysOfWeek = getDaysOfWeek(scanner.nextInt(), scanner.nextInt(), scanner.next());
            System.out.printf(
                    "%d %d %d %d %d %d %d\n",
                    daysOfWeek.get(0),
                    daysOfWeek.get(1),
                    daysOfWeek.get(2),
                    daysOfWeek.get(3),
                    daysOfWeek.get(4),
                    daysOfWeek.get(5),
                    daysOfWeek.get(6)
            );
        }
    }
 
    private static List<Integer> getDaysOfWeek(int m, int d, String s) {
        int pivot = getWeekIndex(s);
 
        List<Integer> ret = new ArrayList<>();
        for (int i = 0; i <= pivot; ++i) {
            int candidate = d - i;
            ret.add(0, (candidate > 0) ? candidate : endDayOfMonths[(m - 2 < 0) ? 11 : m - 2] + candidate);
        }
 
        for (int i = 1, len = 7 - pivot; i < len; ++i) {
            int candidate = d + i;
            ret.add((candidate <= endDayOfMonths[m - 1]) ? candidate : candidate - endDayOfMonths[m - 1]);
        }
 
        return ret;
    }
 
    private static int getWeekIndex(String s) {
        for (int i = 0, len = weekStrings.length; i < len; ++i) if (weekStrings[i].equals(s)) return i;
        throw new IllegalArgumentException();
    }
}
 cs



이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️

반응형

'개발이야기 > 알고스팟' 카테고리의 다른 글

[BRACKETS2] Mismatched Brackets  (0) 2022.01.03
[SHISENSHO] Shisen-sho  (0) 2022.01.03
[CLOCKSYNC] Synchronizing Clocks  (0) 2022.01.02
[HAMMINGCODE] Hamming Code  (0) 2021.12.30
[WEIRD] Weird Numbers  (0) 2021.12.30
Posted by N'
,

[CLOCKSYNC] Synchronizing Clocks

개발이야기/알고스팟2022. 1. 2. 18:33

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
Posted by N'
,

[HAMMINGCODE] Hamming Code

개발이야기/알고스팟2021. 12. 30. 15:05

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

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

 

algospot.com :: HAMMINGCODE

Hamming Code 문제 정보 문제 Jaeha is writing an operating system for his toys, so they will be able to communicate with each other. However, the wireless chips in his toys are very cheap, so they are prone to transmission errors. Quite frequently, Ja

www.algospot.com


풀이입니다. 🤔

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
import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        int[] bits = new int[7];
        Scanner scanner = new Scanner(System.in);
        int cases = scanner.nextInt();
        while (cases-- > 0) {
            char[] input = scanner.next().toCharArray();
            for (int i = 0; i < 7; ++i) {
                bits[i] = input[i] - '0';
            }
 
            int check1 = getXor(bits[0], bits[2], bits[4], bits[6]);
            int check2 = getXor(bits[1], bits[2], bits[5], bits[6]);
            int check3 = getXor(bits[3], bits[4], bits[5], bits[6]);
            int syndrome = 4 * check3 + 2 * check2 + check1;
            if (syndrome != 0) {
                bits[syndrome - 1] = (bits[syndrome - 1] + 1) % 2;
            }
 
            System.out.printf("%d%d%d%d\n", bits[2], bits[4], bits[5], bits[6]);
        }
    }
 
    private static int getXor(int... bits) {
        int ret = bits[0];
        for (int i = 1; i < bits.length; ++i) {
            ret ^= bits[i];
        }
 
        return ret;
    }
}
 cs



이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️

반응형

'개발이야기 > 알고스팟' 카테고리의 다른 글

[WEEKLYCALENDAR] Weekly Calendar  (0) 2022.01.03
[CLOCKSYNC] Synchronizing Clocks  (0) 2022.01.02
[WEIRD] Weird Numbers  (0) 2021.12.30
[XHAENEUNG] 째능 교육  (0) 2021.12.29
[URI] URI Decoding  (0) 2021.12.29
Posted by N'
,
Daum / Designed by i2i Labs

티스토리툴바