[Python] 3이 하나라도 포함되는 모든 경우의 수 - 구현 문제

📌 이 문제는 해당 책에서 가져왔습니다.

문제 설명

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

예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다.

• 00시 00분 03초
• 00시 13분 30초

반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각이다.

• 00시 02분 55초
• 01시 27분 45초

입력 조건

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

출력 조건

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

입력 예시 및 출력

• 입력 예시: 5
• 출력 예시: 11475

문제 해설

이 문제는 모든 시각의 경우를 하나씩 모두 세서 풀 수 있습니다.

왜냐하면 경우의 수는 24 x 60 x 60 으로 86,400개에 밖에 해당되지 않습니다. 따라서 3중 반복문을 이용해 계산할 수 있습니다.

이러한 유형은 완전 탐색 유형으로 분류됩니다.

완전 탐색 알고리즘은 가능한 경우의 수를 모두 검사해보는 탐색 방법입니다.

완전 탐색 문제 또한 구현이 중요한 대표적인 문제 유형인데, 일반적으로 비효율적인 시간 복잡도를 가지므로 데이터 개수가 큰 경우에는 정상적으로 동작하지 않을 수 있습니다.

그러므로 데이터 개수가 100만개 이하일 경우에만 사용하면 적절합니다.

코드 구현

# 시각 문제

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)

---

# 입력값
5
# 출력값
11475

---

해당 문제를 풀기 위해서 알아야 하는 것은 반복문을 겹쳐서 사용할 줄 아는가?

그리고 '3'을 어떻게 찾을 것인가 하는 아이디어이다.

3을 찾기 위해 시간을 '000000'의 6자리 문자열로 바꾼 뒤 if문과 in을 사용해 단순히 확인했다.

그리고 조건이 맞다면 하나씩 count를 증가시키는 방법으로 '3'이 하나라도 포함된 문자열의 개수를 구할 수 있었다.