[백준] 18312번: 시각 (Java)

1. 문제설명

00시 00분 00초부터 N시 59분 59초까지 모든 시각 중에서 K가 하나라도 포함되는 시간들의 수를 구하는 문제이다.

• 시간 제한: 1초
• 메모리 제한: 256MB

 

2. 접근 방식

⇒ 완전탐색을 사용하여 N시 59분 59초까지 모든 시간을 고려한다.

• 3중 for문을 사용해 N시 59분 59초까지 모든 시간의 경우의 수를 고려한다.
• 모든 시간의 각 자리수에 3이 있으면 count를 증가시킨다.

 

3. 최종 코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int N = Integer.parseInt(input[0]);
        int K = Integer.parseInt(input[1]);

        int count = 0; // 결과값 카운트
        for(int h=0; h<=N; h++) { // "시"를 0부터 N까지
            for(int m=0; m<60; m++) { // "분"을 0부터 59까지
                for(int s=0; s<60; s++) { // "초"를 1부터 59까지
                    // 시, 분, 초 중에 각 자리수에 K가 포함되어 있는지 확인
                    if(h/10 == K || m/10 == K || s/10 == K
                    || h%10 == K || m%10 == K || s%10 == K) {
                        count++; // K가 포함되어 있으면 count 증가
                    }
                }
            }
        }

        System.out.println(count);
    }
}

 

4. 시간복잡도

$O(N * 60 * 60)$ 이므로 $O(N * 3600)$