[Python][이코테] 시각

조건

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

 

입력 조건

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

 

출력 조건

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

 

 

입력 예시

5

 

출력 예시

11475

 

---

 

 

단순히 시각을 1씩 증가시키며 3이 하나라도 포함되어 있는지 확인하는 방식으로 풀 수 있다.

 

24 x 60 x 60의 경우의 수를 모두 비교하고

 

3중 반복문을 사용하여 해결한다.

 

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

print(count)

 

사용된 기능

in

 

2022.01.10 - [개발/Python] - [Python] 연산자, in(멤버쉽) 연산자, bool / 예제로 공부하는 Python 100 문제풀이

[Python] 연산자, in(멤버쉽) 연산자, bool / 예제로 공부하는 Python 100 문제풀이

 

in 기능을 몰라서 어떻게 풀어야 하나 막막했다...

 

java에는 indexOf 같은 포함하는지 확인하는 기능이 있지만 파이썬은 아직 익숙지 못해 몰랐다.. 결국 보고 풀었다.

---

이러한 유형은 '완전 탐색' 유형으로 분류된다. 완전 탐색 알고리즘은 가능한 경우의 수를 모두 검사해보는 탐색 방법이다.

 

일반적으로 완전 탐색 알고리즘은 비효율적인 시간 복잡도를 가지고 있으므로 (위의 경우 3중 반복문으로 O(N^3)의 시간 복잡도) 데이터 개수가 큰 경우 정상적으로 동작하지 않을 수 있다. 그래서 일반적으로 알고리즘 문제를 풀 때는 확인해야 할 전체 데이터의 개수가 100만 개 이하일 때 사용하면 좋다.

 

*위의 경우는 24 * 60 * 60 으로 최대 86400의 경우의 수뿐이다.