[이코테] 시각 - Python 풀이

- 문제

 

정수 N이 입력되면 00시 ()()분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포 함되는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 1을 입력했을 때 다음은 3이 하 나라도 포함되어 있으므로 세어야 하는 시각이다.

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

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

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

 

입력 예시

5

 

출력 예시

11475

처음 짠 코드

n = int(input())

count = 0
for i in range(n+1):
    for j in range(60):
        for k in range(60):
            str_list = list(str(i)+str(j)+str(k))
            if '3' not in str_list:
                pass
            else:
                count+=1

print(count)

정답 코드

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)

느낀점

하루는 86,400초이기 때문에 모든 경우의 수를 다 따져도 86,400가지밖에 존재하지 않는다.

모든 경우의 수가 10만개 이하이므로 파이썬에서 문자열 연산을 이용해 모든 경우의 수를 다 따져도 시간 제한 2초 안에 해결할 수 있다.

따라서 단순히 3중 for문으로 돌린 후 int를 str로 바꾸어 '3'이 있는 지를 찾는 비교적 쉬운 문제였지만 괜히 if else 로 쓰지 말고 최대한 간결하게 짜는 연습을 해야겠다.

 

이처럼 완전 탐색 알고리즘은 비효율적인 시간 복잡도를 가지고 있으므로 전체 데이터 개수가 100만 개 이하일 때 이러한 방식을 사용하자.

참고

• 이것이 취업을 위한 코딩 테스트다. with python