시각 [구현]

구현 실전 문제

시각

🐾 문제 설명

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

🐾 입출력 예시

• 입력
  5
• 출력
  11475

🐾 내 풀이

풀이 1) 모든 경우를 확인 하는 풀이

N = int(input())

H, M, S = 0, 0, 0
cnt = 0

while True:
    if ("3" in str(H) or "3" in str(M) or "3" in str(S)):
        cnt += 1
    if H == N and M == 59 and S == 59:
        break
    
    S += 1
    if S == 60:
        S = 0
        M += 1
    if M == 60:
        M = 0
        H += 1

print(cnt)

실제 시간의 흐름에 따라 매초마다 각각의 상황에서의 3 포함여부를 확인하는 코드이다.

풀이 2) 수학적 계산을 통한 풀이

N = int(input())

cnt = 0
for i in range(60):
    for j in range(60):
        if "3" in str(i) + str(j):
            cnt += 1

answer = 0
for i in range(N + 1):
    if "3" in str(i):
        answer += 3600
    else:
        answer += cnt

print(answer)

N에 따라 H값만 변경이 되므로 H에 3이 포함된 경우에는 60초 x 60분의 3600을 더해주고 3이 포함되지 않은 경우에는 00분 00초에서 59분 59초 사이에 3이 포함된 횟수를 더해주도록 한다.

🐾 답안 예시

< 이것이 취업을 위한 코딩 테스트다 with 파이썬 > 답안 예시

# H를 입력받기
h = int(input())

count = 0
for i in range(h + 1):
    for j in range(60):
        for k in range(60):
            # 매 시각 안에 '3'이 포함되어 있다면 카운트 증가
            if '3' in str(i) + str(j) + str(k):
                count += 1

print(count)

예시 답안에서는 완전 탐색을 이용하였다. 시각 문제에서는 모든 가능한 경우의 수가 많지 않으므로 이러한 완전 탐색을 이용할 수 있다.
완전 탐색으로 문제를 풀 경우 시각 복잡도에서 좋은 성능을 보이지 못할 수 있어, 확인(탐색)해야할 전체 데이터의 개수가 100만개 이하인 경우에 사용하면 적절하다.

---

참고자료
이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈