[이것이 코딩 테스트다] 구현 <예제 4-2. 시각>

📚[예제 4-2] 시각

[문제]

정수 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

🔍[답안을 바탕으로 작성한 예시]

n = int(input())

result = 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):
                result += 1


print(result)

📄[문제 해설]

이러한 문제의 유형은 완전 탐색유형으로 분류되기도 한다. 완전 탐색 알고리즘은 가능한 경우의 수를 모두 검사해보는 탐색 방법이다. 완전 탐색 문제 또한 구현이 중요한 대표적인 문제 유형인데, 일반적으로 완전 탐색 알고리즘은 비효율적인 시간 복잡도를 가지고 있으므로 데이터 개수가 큰 경우에는 잘 사용하지 않는다.

위의 소스코드에서는 매 시각을 문자열(string) 으로 바꾼 다음 문자열에 '3'이 포함됐는지 검사한 후 개수를 체크하는 방식이다.

※ 해당 포스팅은「이것이 취업을 위한 코딩테스트다(나동빈 저)」책 내용을 바탕으로 작성하였습니다.