🔖시각
정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오.
예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다.
- 00시 00분 03초
- 00시 13분 30초
🔹 입력조건
첫째 줄에 정수 N이 입력된다. (0 <= N <= 23)🔹 출력조건
00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다.🔹 입력예시
5🔹 출력예시
11475🤔 접근 방향
3이라는 문자열이 시각에 포함되어 있는지를 확인해야 함 ❗
- 시, 분, 초를 1씩 증가시킨다
- 3이라는 문자열이 포함되어 있는지 여부를 확인한다.
- 포함되어 있다면 👉🏻count
- 포함되어 있지 않다면 👉🏻continue
📑 나의 답안
n = int(input())
count = 0
for i in range(n + 1):
for j in range(60):
for k in range(60):
# 매 시각을 문자열로 변환 후 검사
# 03시 20분 35초 -> '032035'
if '3' in str(i) + str(j) + str(k):
count += 1
print(count)👉🏻 예시답안과 동일함
3중 for문을 통해 시, 분, 초를 1씩 증가시키며 '3'이라는 문자열의 포함 여부를 확인
✔ 문제 해설
이 문제는 모든 시각의 경우를 하나씩 모두 세서 쉽게 풀 수 있는 문제이다.
하루는 86,400 초로, 00시 00분 00초 부터 23시 59분 59초 까지의 모든 경우는 86,400 가지 밖에 존재하지 않는다.
즉, 경우의 수가 100,000 개도 되지 않으므로 파이썬에서 문자열 연산을 이용해 시간 제한 2초 안에 문제를 해결할 수 있다.
전체 시, 분, 초에 대한 경우의 수는 24 X 60 X 60 이며 3중 반복문을 이용해 계산할 수 있다.
이러한 유형은 완전 탐색 유형으로 분류되기도 한다.
완전 탐색 알고리즘은 가능한 경우의 수를 모두 검사해보는 탐색 방법이다.
이 알고리즘은 비효율적인 시간 복잡도를 가지고 있으므로 데이터 개수가 큰 경우에 정상적으로 동작하지 않을 수 있다.
그래서 일반적으로 알고리즘 문제를 풀 때는 확인해야 할 전체 데이터 개수가 100만개 이하일 때 완전 탐색을 사용하면 적절하다.
🐾Reference
- 이것이 코딩테스트다 with 파이썬
🐜👣steadiness🐜👣