[이코테] 구현 - 시각.py

이것이 코딩테스트다 - ch04 구현 예제 문제

4-2 시각

문제 설명

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

input

N : N시

output

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

limit

0 <= N <= 23
time : 2 s

구현 코드

Analysis

• time-complexity : O(N)
• space-complexity : O(1)

def solve(N):
    # 완전탐색
    cnt = 0
    for h in range(N + 1):
        for m in range(60):
            for s in range(60):
                if "3" in str(h) + str(m) + str(s):
                    cnt += 1
    return cnt

효율 높이기

완전탐색으로 구현한다면 간단하지만 탐색량이 N * 60 * 60이 된다. 이를 다음과 같은 사항를 이용해서 구현할 수 있다.

• 0~N시 중 3이 포함되어 있다면 모든 분과 모든 초일 때 조건을 달성하므로 60 * 60 = 3600회
• 0~N시 중 3이 포함 되어 있지 않다면 (15 * 60) + (15 * 60) - (15 * 15) = 1575
• 0~59분/초에 3이 포함된 경우 15개 - 3, 13, 23, 43, 53, 30~39

def solve_efficient(N):
    cnt = 0
    cnt_include_3 = 3600
    cnt_not_include_3 = 1575

    for h in range(N + 1):
        if "3" in str(h):
            cnt += cnt_include_3
        else:
            cnt += cnt_not_include_3
    return cnt

테스트 코드

class testSolve(unittest.TestCase):
    def testcase(self):
        self.assertEqual(solve(5), 11475)


unittest.main()