[Algorithm] 알고리즘 구현 유형 문제 풀이 - 시각 문제

'이것이 취업을 위한 코딩 테스트다 with 파이썬' 이라는 책을 공부 중입니다. 이 글은 해당 책에서 알고리즘 구현 유형 문제 중 ' 시각' 문제와 풀이를 설명합니다.

 

문제

 

🎁입력 조건

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하라. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다

00시 00분 03초

00시 13분 30초

 

반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각이다

00시 02분 55초

01시 27분 45초

 

🎁입력 조건

첫째 줄에 정수 N이 입력된다. (0 <= N <= 23)

 

🎊출력 조건

00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다. 시간 제한은 2초, 메모리 제한은 128MB로 한다.

 

🎁입력 예시

5

🎊출력 예시

11475

 

문제 해설

문제를 해결하기 위한 아이디어는 여러가지가 있을 것이다. 이 글에서는 두 가지의 아이디어를 제공한다. 

 

1. 완전 탐색으로 모든 경우의 수 고려하기 (저자의 아이디어)

2. ‘시’, ‘분’, ‘초’의 숫자 3이 포함되거나 미포함되는 경우를 나누어 생각하기 (나의 아이디어)

 

저자는 첫 번째 아이디어인 완전 탐색을 통해 문제를 해결한다. 하루는 86,400초로 00시 00분 00초부터 23시 59분 59초까지 초든 경우는 86,400까지밖에 존재하지 않는다. 이 정도 경우의 수는 문자열 연산을 이용해 3이 시각에 포함되어 있는지 확인해도 시간 제한 2초 안에 문제를 해결할 수 있다.

 

import java.util.Scanner;

 

public class 시각1 {

    // 특정한 시각 안에 '3'이 포함되어 있는지의 여부
    public static boolean check(int h, int m, int s) {
        if (h % 10 == 3 || m / 10 == 3 || m % 10 == 3 || s / 10 == 3 || s % 10 == 3)
            return true;
        return false;
    }

    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt(); // 0 <= N <= 23

        int count = 0;
        for(int i = 0; i <= N; i++)
            for(int j = 0; j <= 59; j++)
                for(int k = 0; k <= 59; k++){
                    //매 시각 안에 '3'이 포함되어 있다면 카운트 증가
                    if (check(i, j, k)) count++;
                }

        System.out.println(count);
    }
}

 

두 번째 아이디어로 ‘시’, ‘분’, ‘초’에 3이 포함되어 있거나 미포함되어 있는 경우를 나누어 생각하는 방법이다.

 

‘시’에 3이 포함되어 있는 경우는 ‘시’가 3, 13, 23일 때로 3가지이며, 이때는 ‘분’과 ‘초’에 상관없이 모든 경우를 더한다(60 * 60).

 

‘시’에 3이 포함되어 있지 않은 경우 ‘분’과 ‘초’에 3이 포함되어있는 경우를 생각한다. ‘분’에 3이 포함되어 있는 경우는 3, 13, 23, 30~39, 43, 53일  때로 15가지이며, 이때는 ‘초’에 상관없이 모든 경우를 더한다(15 * 60).

‘분’에 3이 포함되어 있지 않은 경우는 45가지(60-15)이며, 이때는 ‘초’가 3이 포함되어있는 경우를 고려한다. 3, 13, 23, 30~39, 43, 53일 때로 15가지다(45*15).

 

이러한 모든 경우를 계산하면 아래와 같은 코드로 표현할 수 있다. 

 

import java.util.Scanner;



public class 시각2 {

   public static void main(String args[]){

       Scanner scanner = new Scanner(System.in);
       int N = scanner.nextInt(); // 0 <= N <= 23

       int count = 0;

       for(int i =0; i <= N; i ++){
           if(i == 3 || i == 13 || i == 23){ //'시'에 숫자 3이 포함되어 있는 경우
               count = count + 60*60;
           }else{ //'시'에 숫자 3이 포함되지 않는 경우
               //'분'에 숫자 3이 포함(3,13,23,30~39,43,53)되는 경우 15 * 60
               //'분'에 숫자 3이 미포함되면서 '초'에 숫자 3이 포함되는 경우 45 * 60
               count = count + (15 * 60) + (45 * 15);
           }
       }
       
       System.out.println(count);

   }
}

 

저자 풀이

https://github.com/ndb796/python-for-coding-test/blob/master/4/2.java

 

출처

이것이 코딩 테스트다