[백준] 타임머신 - 1440번

타임머신

2 초	128 MB	1932	861	742	46.814%

문제

다솜이는 타임머신을 타고 8364년으로 갔다. 다행히 지구는 평화롭다.

다솜이는 2008년으로 돌아가기 전에 시계를 샀다. 다솜이는 시계를 볼 줄 모르기 때문에, 디지털 시계를 샀다. 디지털 시계는 HH:MM:SS와 같은 모양으로 시간을 나타내 준다. 그리고 앞에서부터 차례대로 HH는 시, MM은 분, SS는 초를 나타낸다.

다솜이는 8364년에는 2008년과 같은 방법으로 시간을 나타내는지 모른다. 2008년엔 시:분:초를 나타내는지만, 8364년엔 분:시:초로 나타낼지도 모른다.

다행히 시는 01부터 12, 분은 00부터 59, 초는 00부터 59를 나타낸다.

다솜이의 시계에 쓰여 있는 숫자가 주어졌을 때, 이 시간을 읽을 수 있는 가능한 방법의 수를 출력하는 프로그램을 작성하시오. 나타내는 시간이 같더라도, 시, 분, 초를 읽을 수 있는 위치가 다르면 다른 방법으로 센다. 또한, 방법의 수가 0일 수도 있다.

예를 들어, 21:23:01 은 21분 23초 01시 로 읽을 수도 있지만, 21초 23분 01시로 읽을 수도 있다.

입력

첫째 줄에 시간이 주어진다. 시간은 DD:DD:DD와 같은 꼴로 주어진다. 항상 8자리(:도 포함)로만 들어오며, D는 0-9 사이의 숫자이다.

출력

첫째 줄에 시간을 읽을 수 있는 가능한 방법의 수를 출력한다.

예제 입력 1 복사

00:00:00

예제 출력 1 복사

0

예제 입력 2 복사

01:00:00

예제 출력 2 복사

2

예제 입력 3 복사

01:12:23

예제 출력 3 복사

4

예제 입력 4 복사

21:23:01

예제 출력 4 복사

2

예제 입력 5 복사

01:02:03

예제 출력 5 복사

6

예제 입력 6 복사

59:59:01

예제 출력 6 복사

2

예제 입력 7 복사

01:01:59

예제 출력 7 복사

4

알고리즘 분류

• 구현
• 브루트포스 알고리즘

코드

// 메모리 : 17700KB
// 시간 : 204MS

package 타임머신;

import java.util.Scanner;

/*
[시간복잡도]
    [구성]
        - 시간 문자열 처리: 문자열 길이만큼 반복 (O(n))
        - 시간 조합 생성: 6가지 조합 생성 (O(1))
        - 유효한 시간 조합 확인: isValidTime 함수 호출 (O(1)) - 각 조합에 대해 한 번만 호출됨
        - 카운터 증가: 상수 시간 연산 (O(1))

    [시간 복잡도 계산]
        - 시간 문자열 처리: 입력 문자열 길이가 n이라고 가정하면 O(n) 시간이 소요됩니다.
        - 시간 조합 생성: 6가지 조합을 생성하는데 O(1) 시간이 소요됩니다.
        - 유효한 시간 조합 확인: 각 조합에 대해 isValidTime 함수를 호출하는데 O(1) 시간이 소요됩니다.
            입력 문자열 길이가 n이라면 최대 n번 호출되므로 O(n) 시간이 소요됩니다.
        - 카운터 증가: 상수 시간 연산이므로 O(1) 시간이 소요됩니다.

        결론 : 최악의 경우 시간 복잡도는 O(n) + O(n) = O(n)이라고 결론 지을 수 있습니다.
 */

public class Main {

    /**
     * 주어진 시간 (시, 분, 초) 값이 유효한지 확인하는 메서드입니다.
     * 유효한 시간은 시는 1부터 12까지, 분과 초는 0부터 59까지 입니다.
     */
    public static boolean isValidTime(int h, int m, int s) {
        boolean isHourValid =  (1 <= h && h <= 12);
        boolean isMinuteValid =  (0 <= m && m <= 59);
        boolean isSecondValid =  (0 <= s && s <= 59);
        return  isHourValid && isMinuteValid && isSecondValid;
    }

    /**
     * 주어진 시간 문자열에서 가능한 모든 유효한 시간 조합의 개수를 세는 메서드입니다.
     *
     * @param timeStr 시간 문자열 (예: "12:34:56")
     * @return 주어진 시간 문자열에서 만들 수 있는 유효한 시간 조합의 개수
     */
    public static int countValidTimeCombinations(String timeStr) {
        int h1 = Character.getNumericValue(timeStr.charAt(0)); // 첫 번째 시각 숫자
        int h2 = Character.getNumericValue(timeStr.charAt(1)); // 두 번째 시각 숫자
        int m1 = Character.getNumericValue(timeStr.charAt(3)); // 첫 번째 분 숫자
        int m2 = Character.getNumericValue(timeStr.charAt(4)); // 두 번째 분 숫자
        int s1 = Character.getNumericValue(timeStr.charAt(6)); // 첫 번째 초 숫자
        int s2 = Character.getNumericValue(timeStr.charAt(7)); // 두 번째 초 숫자

        // 가능한 시간 조합 (각 조합은 시:분:초 순서를 나타냅니다)
        int[][] combinations = {
                {h1 * 10 + h2, m1 * 10 + m2, s1 * 10 + s2}, // HH:MM:SS
                {h1 * 10 + h2, s1 * 10 + s2, m1 * 10 + m2}, // HH:SS:MM
                {m1 * 10 + m2, h1 * 10 + h2, s1 * 10 + s2}, // MM:HH:SS
                {m1 * 10 + m2, s1 * 10 + s2, h1 * 10 + h2}, // MM:SS:HH
                {s1 * 10 + s2, h1 * 10 + h2, m1 * 10 + m2}, // SS:HH:MM
                {s1 * 10 + s2, m1 * 10 + m2, h1 * 10 + h2}  // SS:MM:HH
        };

        int validCount = 0;
        for (int[] combination : combinations) {
            int h = combination[0]; // 현재 조합의 시
            int m = combination[1]; // 현재 조합의 분
            int s = combination[2]; // 현재 조합의 초

            if (isValidTime(h, m, s)) {
                validCount += 1;
            }
        }

        return validCount;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String timeStr = scanner.nextLine().trim();
        scanner.close();

        int result = countValidTimeCombinations(timeStr);
        System.out.println(result);
    }
}