[이취코테] 시각

https://youtu.be/2zjoKjt97vQ

이 문제의 해설 영상이다.

문제

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오.

 

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

 

출력 조건: 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다.

 

정답 코드

n = int(input())
cnt = 0

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

print(cnt)

이 문제는 모든 시각의 경우를 하나씩 모두 세서 푸는 완전탐색(Brute Forcing) 유형이다. 완전탐색 알고리즘은 일반적으로 비효율적인 시간 복잡도를 가지고 있으므로 데이터의 개수가 100만 개 이하일 때 완전 탐색을 사용하면 적절하다. 

 

이 문제에서 모든 경우의 수는 24 x 60 x 60 = 86,400 개 밖에 되지 않으므로 완전 탐색을 이용하기 적절하다.나는 완전탐색을 이용하는 문제를 이번 문제로 처음 접해봐서 더 효율적인 아이디어를 떠올리다가 구현에 실패했다. 그렇다보니 정답코드를 보고나니 약간 허탈했다.

 

 

배울 점

완전 탐색 문제를 더 풀어보면서 앞으로 어떤 경우에 완전탐색을 이용해야 되는지 원활하게 판단하고 사용할 수 있도록 해야겠다. 

 

---

참고자료: 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 지음(한빛미디어)