🚀문제

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

• 00시 00분 03초
• 00시 13분 30초

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

• 00시 02분 55초
• 01시 27분 45초

ex

입력

5

출력

11475

📝 내 생각과 풀이

완전탐색으로 푸는건진 모르겠는데 일일히 해보도록하자

# N을 입력받기
n = int(input())
count=0
for i in range(n+1):
    for j in range(60):
        for k in range(60):
            if '3' in str(i)+str(j)+str(k):
                count+=1
print(count)

문제 해설

이 문제는 모든 시각의 경우를 하나씩 모두 세서 쉽게 풀 수 있는 문제다. 왜냐하면 하루는 86400초로, 00시 00분 00초 부터 24시 59분 59초까지의 모든 경우는 86400가지밖에 존재하지 않기 때문이다. 다시말해 경우의 수가 100,000개도 되지 않으므로 파이썬에서 문자열 연산을 이용해 3이 시각에 포함되어있는지 확인해도 시간제한 2초안에 해결할 수 있다.
따라서 단순히 시각을 1씩 증가시키면서 3이 하나라도 포함되어있는지 확인하면 될 것이다. 전체 시, 분, 초에 대한 경우의 수는 24x60x60이며 3중 반복문을 이용해 계산할 수 있다.
완전탐색 유형은 비효율적인 시간 복잡도를 가지고 있으므로 데이터개수가 큰 경우에 정상적으로 동작하지 않을 수있다. 그래서 일반적으로 알고리즘 문제를 풀 때는 확인(탐색) 해야 할 전체 데이터의 개수가 100만개 이하일때 완전탐색을 사용하면 적적하다.

Think

완전탐색해도 되는지 안되는지 직접 갯수를 세어보고나서 판단할 수 있어야겠다.

문제 출처 : 이것이 취업을 위한 코딩테스트다 (저자 : 나동빈)