📖문제

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

입력 조건

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

출력 조건

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

📝풀이과정

• 1시간 당 3이 하나라도 포함되어있는 시간의 개수를 미리 구해두었다.
• '시' 단위에 3이 포함되어있지 않은 경우 (1575)

'분'단위에 3이 있는지	'시'단위에 3이 있는지	개수
O	X	15 x 45 = 675
X	O	45 x 15 = 675
O	O	15 x 15 = 225

• '시' 단위에 3이 포함되어있는 경우 (60 x 60 = 3600)

따라서 00시 00분 00초부터 N시 59분 59초까지 '시'에 3이 있는지 없는지 여부를 기준으로 3600과 1575를 결과값에 더해가면서 답을 구했다.

⌨코드1 (내 코드)

n = int(input())

answer = 0
# i가 0부터 n까지
for i in range(n + 1):
  # '시'에 3이 포함되어있으면 변수 answer에 3600 더하기
  if i % 10 == 3:
    answer += 3600
  
  # '시'에 3이 포함되어있지 않으면 변수 answer에 1575 더하기
  else:
    answer += 1575

print(answer)

⌨코드2 (책 예시 코드)

• 이 문제의 제한 시간은 2초이고, 00시 00분 00초부터 23시 59분 59초까지의 모든 경우는 86400(24 x 60 x 60)가지밖에 되지 않으므로,
  모든 시간을 for문을 통해 일일이 확인해도 제한 시간 안에 답을 구할 수 있다.

h = int(input())

count = 0
for i in range(h + 1):
	for j in range(60):
    	for k in range(60):
        	# 매 시각 안에 '3'이 포함되어 있다면 카운트 증가
            	if '3' in str(i) + str(j) + str(k):
                	count += 1
                    
print(count)

💡새로 알게된 문법

문자열 검사

• in 사용
• 특정 문자(열)가 문자열 안에 있는지 검사할 때 사용
• 예시
  문자열 str(i) + str(j) + str(k) 안에 '3'이 있으면 count 1 증가

if '3' in str(i) + str(j) + str(k):
	count += 1

☺ 느낀점

내가 문제를 처음 딱 봤을 때 어떻게 하면 이 문제를 더 빠른 시간에 풀 수 있을지부터 고민하는 것 같다. 그래서 미리 더해질 숫자들을 구해놓고 정답을 담는 변수에 더하는 식으로 문제를 풀게 되었다.
완전 탐색으로 풀어도 제한 시간 안에 답을 구할 수 있다면, 완전 탐색으로 푸는 것이 아이디어를 코드로 풀어내는 게 더 쉽기 때문에 문제를 푸는 속도를 줄일 수 있다.
알고리즘에는 '완전 탐색'도 있다는 것을 염두에 두도록 하자~