[Python] 구현 및 시뮬레이션 알고리즘을 파헤쳐 보자! (시각)

문제

• 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하세요. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각입니다.
  • 00시 00분 03초
  • 00시 13분 30초
• 반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각입니다.
  • 00시 02분 55초
  • 01시 27분 45초

입력

5

출력

11475

내가 제출한 풀이 - 정답

import sys

n = int(sys.stdin.readline().strip())
result = 0

for i in range(0, n + 1):
	# 1시간이 3600초
    if i % 10 == 3:
        result += 3600
        continue

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

정답

import sys

n = int(sys.stdin.readline().strip())
result = 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):
                result += 1
                
print(result)

Tip

모든 시간의 경우를 하나씩 비교하여 풀어야 하는 문제이며, 완전 탐색(브루트 포스)을 이용한 풀이였다.

하루는 86,400초이므로, 어떠한 숫자가 들어와도 고정적으로 86,400가지의 경우만 보면 되기 때문에 완전 탐색기법을 사용해도 됐다.

# 1시간이 3600초
if i % 10 == 3:
	result += 3600
	continue

완전탐색을 사용 안 하고 3만 찾는 공식을 생각하다가 전혀 나오지 않아 완전 탐색을 사용하였다. 그래도 최소한의 반복을 위해 3, 13, 23 시간은 모든 시간이 포함이 되므로 3600을 더하고 continue 하였다. (이렇게 풀어도 될라나...?)

 

문자열 합치기

# i = 1, j = 2, k = 3
'3' in str(i) + str(j) + str(k)
#'123'

숫자를 문자열로 바꿔 해당 모든 문자열을 합쳐 3이 있는지 확인했다.

   References

본 그리디 알고리즘 문제 예제 및 개념은 나동빈 (이코테 2021 강의 몰아보기)  2. 그리디 & 구현을 참고합니다.