구현 : 시뮬레이션과 완전 탐색 - 시각 문제

문제 설명

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

# 입력 조건

• 첫째 줄에 정수 N이 주어진다. ( 0<=N<=23 

# 출력 조건

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

입력 예시	출력 예시
5	11475

 

 

문제 해결 아이디어

• 완전 탐색(Brute Focing) 유형 : 가능한 모든 경우의 수를 모두 검사해보는 탐색 방법
• 단순히 시각을 1씩 증가시키며 3이 하나라도 포함되어 있는지 확인

풀이1  :  삼중포문

h = int(input())
count = 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):
                count+=1
print(count)

 

풀이2  :  좀 더 빠른 O(n)의 시간복잡도

n = int(input('n입력: '))
cnt=0
for i in range(1,(n*10000+5960)):
    if (i//1000) %10>=6 : continue
    if (i//10)%10>=6: continue
    if (i%10)==3 :
        cnt+=1
        continue
    elif (i//10)%10==3 :
        cnt+=1 
        continue
    elif (i//100)%10==3 :
        cnt+=1 
        continue
    elif (i//1000) %10==3 :
        cnt+=1 
        continue
    elif (i//10000) %10==3 :
        cnt+=1 
        continue
print(cnt)