구현 - 시각

문제 해설: 이 문제는 시각을 1씩 증가시키면서 3이 하나라도 포함되어 있는지 확인하면 된다. 전체 시, 분, 초에 대한 경우의 수는 24 x 60 x 60이며 3중 반복문을 이용해 계산할 수 있다.

이러한 유형은 완전 탐색 유형으로 분류되기도 한다. 일반적으로 완전 탐색 알고리즘은 비효율적인 시간 복잡도를 가지고 있으므로 데이터 개수가 큰 경우에 정상적으로 동작하지 않을 수 있다. 그래서 일반적으로 알고리즘 문제를 풀 때는 확인(탐색) 해야 할 전체 데이터의 개수가 100만 개 이하일 때 완전 탐색을 사용하면 적절하다.

다음 소스코드에서는 매 시각을 문자열로 바꾼 다음 문자열에 '3'이 포함됐는지 검사한다. 다시 말해 00시 00분 00초부터 23시 59분 59초까지 1초씩 늘리며 시, 분, 초를 문자열 자료형으로 변환하여 합친다.

ex) 03시 20분 35초일 때를 확인하면, 이를 '032035'로 만들어서 '3'이 '032035'에 포함되어 있는지를 체크하는 방식을 이용한다.

h = int(input())
cnt = 0

for i in range(h + 1):
    for j in range(60):
        for k in range(60):
            if '3' in str(i)+str(j)+str(k):
                cnt += 1
print(cnt)

출처: 나동빈, 『이것이 취업을 위한 코딩 테스트다 with 파이썬』(한빛미디어), 113-114p