[이코테] 시각

출처: 이것이 취업을 위한 코딩테스트다  with 파이썬 (나동빈)

https://www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=2

 

문제

• 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하세요. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각입니다.
  • 00시 00분 03초
  • 00시 13분 30초
• 반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각입니다.
  • 00시 02분 55초
  • 01시 27분 45초

 

문제 조건

• 풀이 시간: 15분
• 시간 제한: 2초
• 메모리 제한: 128MB
• 입력 조건: 첫째 줄에 정수 N이 입력됩니다. (0<=N<=23)
• 출력 조건: 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력합니다.

 

---

작성 코드

 

그냥 단순 구현 문제같았고

00시 00분 00초부터 N시 59분 59초 범위 내에서

(가능한 모든 시각 개수) - (3이 단 하나도 포함되지 않는 시각 개수) 를 계산하여 출력하였다.

 

가능한 모든 시각은

시: 0~n까지 들어올 수 있으므로 --> n+1가지

분: 십의자리수 0~5까지, 일의자리수 0~9까지 들어올 수 있으므로--> 6 * 10 = 60가지

초: 십의자리수 0~5까지, 일의자리수 0~9까지 들어올 수 있으므로 --> 6 * 10 = 60가지

따라서 가능한 모든 시각의 개수 = (n+1) * 60 * 60 가지가 된다.

 

3이 단 하나도 포함되지 않는 시각은

각 자리에 들어올 수 있는 숫자중 3만 제외하고 경우의 수를 구하면 된다

따라서

시: 주어진 n이 0~2인 경우 --> 0~n까지 모두 들어올 수 있으므로 (n+1)가지

     주어진 n이 3~12인 경우 --> 3 빼고 다 들어올 수 있으므로 (n+1)-1  = n가지

     주어진 n이 13~22인 경우 --> 3, 13 두 숫자 빼고 다 들어올 수 있으므로  (n+1)-2 = (n-1)가지

     주어진 n이 23인 경우 --> 3, 13, 23 세 숫자 빼고 다 들어올 수 있으므로 (n+1)-3 = (n-2)가지

분: (6-1)*(10-1)=45가지

초: 5*9=45가지

따라서 3이 단 하나도 포함되지 않는 시각 개수는 시, 분, 초의 경우를 모두 곱한 수가 된다.

 

 

가능한 모든 시각과, 3이 단 하나도 포함되지 않는 시각 중 분*초를 계산하는 식은 n의 범위에 따라서 변하지 않는다.

그래서 이 식들을 변수 all, temp에 각각 미리 저장해놓고

n범위에 따라서 temp에 n-2 ~ n+1 중 어떤 값을 추가로 곱해줄지만 결정하여 결과를 출력했다

 

n = int(input())

all = (n+1)*6*10*6*10 #가능한 모든 시각
temp = 5*9*5*9 #3 단 한개도 포함 안 하는 분,초

if n<3:
  print(all - (n+1) * temp)
elif 3<=n<13:
  print(all - n * temp)
elif n==23:
  print(all - (n-2) * temp)
else: 
  print(all - (n-1) * temp)

 

---

강의 예시 답안

하루는 60*60*24 = 86400초밖에 안 되기 때문에

모든 경우를 하나하나 일일히 다 따져도 86400번만 수행하면 되므로 제한 시간 내에 충분히 풀 수가 있다.

(파이썬은 1초에 약 2000만번의 연산을 수행하니까)

 

그래서 단순히 시각을 1씩 증가시키면서, 3이 하나라도 포함되어 있는지를 체크하고

3이 포함되어 있으면 카운트를 증가시켜줬다

---

나랑은 다르게 엄청 간단하게 생각하여 바로 푸신 것 같아서 신기했다

 

강의/교재에서처럼 문제를 풀면

내가 푼 방법과는 다르게 경우를 나누고 그에 따른 경우의 수를 따져볼 필요가 없어서,

문제풀이 시간이 확 줄어들 것 같다.

 

저렇게 단순하게 생각하여 코드를 짜도 제한시간 내에 파이썬이 연산을 수행할 수 있는지 미리 따져보는 습관을 갖는다면

문제 풀이 시간을 많이 단축할 수 있을듯!