백준 3154 : 알람시계

문제 링크

알고리즘 재활 훈련으로 가져온 문제인데...
브론즈문제 라기에는 생각할 건덕지가 좀 많았다.

브론즈 답지않게 문제의 문장 길이도 길거니와... 일단 부딪혀보지 않으면 뭘 어떻게 하라는건지 감이 잘 안 온다.

논리 전개 과정

1. 만들 수 있는 답이 여러 가지라 한다. 이를 먼저 생각해보면 앞의 시를 표시하는 자릿 수는 24에 대한 나머지와 같기만 하면 된다. 즉, 입력1로 주어진 14:19에서 14는 (14, 38, 62, 86), 총 4가지로 표현이 되며, 19는 (19, 79), 2가지로 표현이 된다. 4 X 2 = 8가지로 답의 조합이 나온다는 것임을 알 수 있으며, 이를 통해 2중 for문을 사용해 풀어볼 수 있겠다라는 논리가 도출된다.

for (int HH = H; HH < 100; HH += 24) {
            for (int MM = M; MM < 100; MM += 60) {
            int e = effort(HH, MM);
        }
     }

여기서 effort라는 메서드를 구현할 것인데, 다음과 같이 코드로 구현한다.

    static int effort(int hh, int mm) {
        int distance = 0;

        int a = hh / 10;
        int b = hh % 10;
        int c = mm / 10;
        int d = mm % 10;

        distance = distDigit(a, b) + distDigit(b, c) + distDigit(c, d);

        return distance;
    }

a, b, c, d를 보면 각 자릿수를 쪼갠 것과 같다. 이를 다시 distDigit라는 메서드를 이용해 맨헤탄 거리를 구할 것이다.
※ 맨헤탄 거리란 좌표 간의 거리를 절댓값으로 구한 것을 말한다.
여기서 맨헤탄 거리를 이용하기 전에 좌표 배열을 만든다.

    static int[][] dial = {{3, 1}, {0, 0}, {0, 1}, {0, 2}, {1, 0}, {1, 1}, {1, 2}, {2, 0}, {2, 1}, {2, 2}};
                        // 0        1       2       3       4       5       6       7       8       9

다이얼 좌표이며 1을 기준으로 (0, 0) 설정했다.

    static int distDigit(int x, int y) { // 맨하탄 거리
        int[] p1 = dial[x];
        int[] p2 = dial[y];
        return Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);
    }

각 자리를 절댓값 처리해 더하는 메서드이다.
이를 통해 distance를 구하게 된다.
그러면 이제 이 distance(문제에서는 effort인데 처음 문제에서 명명을 잘못한 바람에 distance가 됐네요.)를 계속 비교하며 최소 힘을 찾으면 됩니다.
minEffort를 설정하지 않는다면, 처음의 e값과 비교할 수가 없습니다. 이를 위해 Integer.MAX_VALUE로 설정해 처음의 e를 저장합니다. 이후 e가 최소치로 갱신이 된다면, 최적 시간과 분을 갱신합니다.
만일 이전 최소치와 현재 최소치의 값이 같다면? 문제에서 제일 빠른 시각을 답으로 도출하라고 했습니다.

최종 코드

import java.io.*;
import java.util.*;

public class Main {

    static int[][] dial = {{3, 1}, {0, 0}, {0, 1}, {0, 2}, {1, 0}, {1, 1}, {1, 2}, {2, 0}, {2, 1}, {2, 2}};
                        // 0        1       2       3       4       5       6       7       8       9

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), ":");
        int H = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int minEffort = Integer.MAX_VALUE;
        int bestH = -1;
        int bestM = -1;

        for (int HH = H; HH < 100; HH += 24) {
            for (int MM = M; MM < 100; MM += 60) {
                int e = effort(HH, MM);

                if (e < minEffort) {
                    minEffort = e;
                    bestH = HH;
                    bestM = MM;
                } else if (e == minEffort) { // 최소 힘이 같다면 가장 빠른 시간을 나타낸다.
                    if (HH < bestH || (HH == bestH && MM < bestM)) {
                        bestH = HH;
                        bestM = MM;
                    }
                }
            }
        }
        System.out.printf("%02d:%02d", bestH, bestM);

    }

    static int effort(int hh, int mm) {
        int distance = 0;

        int a = hh / 10;
        int b = hh % 10;
        int c = mm / 10;
        int d = mm % 10;

        distance = distDigit(a, b) + distDigit(b, c) + distDigit(c, d);

        return distance;
    }

    static int distDigit(int x, int y) { // 맨하탄 거리
        int[] p1 = dial[x];
        int[] p2 = dial[y];
        return Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);
    }
}