제한 조건
- 풀이 시간 : 15분
- 시간 제한 : 2초
문제
정수 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이 하나라도 포함되는 모든 경우의 수를 출력한다.
예시
| 입력 | 출력 |
|---|---|
| 5 | 11475 |
풀이
각 시, 분, 초에서 3이 있는 경우와 없는 경우로 분리하여 경우의 수를 구하면 O(N)으로 풀이가 가능하다고 생각했다.
-
초에 3이 있는 경우
초에 3이 있는 경우는 10초대와 1초대로 분류할 수 있다.
1초대의 경우는03 13 23 33 43 53으로 6개가 존재한다.
10초대의 경우는30 31 32 33 34 35 36 37 38 39으로 10개가 존재하나 1초대에 33이 이미 카운트됐으므로 9개가 존재한다.
결과적으로 초에 3이 있는 경우는 총 15개다. -
분에 3이 있는 경우
분에 3이 있는 경우는 모든 초를 다 카운트하므로 60개다. -
분에 3이 없는 경우
분에 3이 없는 경우는 초에 3이 있는 경우와 동일하므로 15개다. -
시에 3이 있는 경우
시에 3이 있는 경우는 모든 분,초를 다 카운트 하므로 60*60인 3600개다. -
시에 3이 없는 경우
시에 3이 없는 경우는(분에 3이 있는 경우의 수 * 모든 초(60)) + (분에 3이 없는 경우의 수 * 초에 3이 있는 경우의 수(15))이므로(15 * 60) + (45 * 15)인 1575개다.
결과적으로 0시부터 입력되는 N시를 포함하는 시간까지 3이 있는 경우의 수와 없는 경우의 수를 찾아 각 경우의 수를 더해주면 된다.
이슈
문제를 풀고나서 해설을 확인해봤는데, 단순하게 3중 for문을 사용해서 각 시,분,초에 3이 존재하는지 확인하고 있다. 입력받는 시간의 범위가 0-23으로 정해져 있고, 분/초 또한 최대 크기가 60이다. 즉, 아무리 많이 연산해봐야 24 * 60 * 60 = 86400개 밖에 되지 않는다는 것이다. 그러므로 총 경우의 수가 10만개도 되지 않으므로 3중 for문을 활용해 모든 경우의 수를 계산해도 2초 안에 풀이가 가능하다. 이런 방식의 풀이를 완전 탐색이라고 한다.
완전 탐색 알고리즘은 비효율적인 시간 복잡도를 가지나 탐색해야 할 경우의 수가 100만개 이하라면 완전 탐색을 선택할 수 있다.
이 해설을 보고나서 깨달은 것은 무조건 더 좋은 시간 복잡도를 선택할 필요는 없다는 것이다. 코딩 테스트의 목표는 더 빠르고 더 좋은 알고리즘을 만드는 것이 것이 아닌 현재 상황에 맞는 가장 합리적인 방법을 찾아 문제를 해결하는 것이기 때문이다. 그래서 문제의 제한 조건이 여유가 있고, 입력값의 범위가 충분히 작다면 시간 복잡도가 좀 더 높아도 더 빠르고 단순하게 접근하여 풀이가 가능하다면 굳이 시간을 투자해 더 빠른 알고리즘을 구현할 필요는 없다.
코드
