[백준] 18312. 시각

문제 링크

[백준] 18312. 시각

풀이 과정

완전 탐색 문제입니다. 두 가지 방법으로 풀었습니다.

1. 문자열의 format()과 indexOf() 메서드를 이용
2. 시간의 특징을 이용

문자열의 format()과 indexOf() 메서드를 이용

for (int i = 0; i <= N; i++) {
    for (int j = 0; j <= 59; j++) {
        for (int k = 0; k <= 59; k++) {
            String tmp = String.format("%02d", i) + String.format("%02d", j) + String.format("%02d", k);
            if (tmp.indexOf(String.valueOf(K)) != -1) cnt++;
        }
    }
}

시간 hour는 00시에서 N시까지, 분 min은 00분에서 59분까지, 초 sec은 00초에서 59초까지 가능합니다. for문을 숫자로 순회하기에, format()을 이용해 두 자리 수로 변환해줍니다. 이후, 만들어진 문자열에 indexOf()를 사용해 K가 등장하는 지 확인합니다.

24*60*60번 동안 매 번 스트링을 만듭니다. format()을 호출한 결과를 새로운 문자열로 만들고, 또 이어 붙이고 해서 문자열 tmp를 완성합니다. K를 문자열로 만든 뒤, 만들어진 tmp 를 indexOf()로 순회하면서 K를 찾습니다. 이 방법으로는 1924ms 가 소요되어 꽤 많은 시간이 걸린다는 것을 확인할 수 있습니다.

시간의 특징을 이용

1시간은 3600초, 1분은 60초입니다.

K가 시간에서 매칭되면, 00분 00초에서 59분 59초까지 3600번의 같은 매칭 결과가 등장하게 됩니다. 만약, K가 분에서 매칭되면, 00초에서 59초까지 60번의 같은 매칭 결과가 등장하게 됩니다.

for (int hour = 0; hour <= N; hour++) {
    if (hour % 10 == K || hour / 10 == K) {
        cnt += 3600;
    } else {
        for (int min = 0; min < 60; min++) {
            if (min % 10 == K || min / 10 == K) {
                cnt += 60;
            } else {
                for (int sec = 0; sec < 60; sec++) {
                    if (sec % 10 == K || sec / 10 == K) {
                        cnt++;
                    }
                }
            }
        }
    }
}

위 설명을 코드로 작성한 것입니다.

• 두 자리로 표현 가능한 hour의 어느 한 자리에서 K가 발견된다면, 3600을 더해준다.
• 그렇지 않다면, min을 확인한다.
  • 두 자리로 표현 가능한 min의 어느 한 자리에서 K가 발견된다면 60을 더해준다.
  • 그렇지 않다면, sec을 확인하며 1씩 더해준다.

위 코드에서 hour 혹은 min에서 K가 발견되면, 아래를 확인하지 않고 각각 3600, 60만큼을 더한 후 넘어갑니다. 이처럼, 가지치기를 해준 코드는 112ms 밖에 소요되지 않았습니다.

코드

문자열의 format()과 indexOf() 메서드를 이용

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int cnt = 0;

        for (int hour = 0; hour <= N; hour++) {
            for (int min = 0; min <= 59; min++) {
                for (int sec = 0; sec <= 59; sec++) {
                    String tmp = String.format("%02d", hour) + String.format("%02d", min) + String.format("%02d", sec);
                    if (tmp.indexOf(String.valueOf(K)) != -1) cnt++;
                }
            }
        }

        System.out.println(cnt);
    }
}

시간의 특징을 이용

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int cnt = 0;

        for (int hour = 0; hour <= N; hour++) {
            if (hour % 10 == K || hour / 10 == K) {
                cnt += 3600;
            } else {
                for (int min = 0; min < 60; min++) {
                    if (min % 10 == K || min / 10 == K) {
                        cnt += 60;
                    } else {
                        for (int sec = 0; sec < 60; sec++) {
                            if (sec % 10 == K || sec / 10 == K) {
                                cnt++;
                            }
                        }
                    }
                }
            }
        }

        System.out.println(cnt);
    }
}