Python 59 - 구현 시각 문제 ( 알고리즘 )

난이도 ●○○       l       풀이 시간 15분       l       시간 제한 2초       l       메모리 제한 128MB

 

정수 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이 하나라도 포함되는 모든 경우의 수를 출력한다.

문제 해설

이 문제는 모든 시각의 경우를 하나씩 모두 세서 쉽게 풀 수 있는 문제다. 왜냐하면 하루는 86,400초로, 00시 00분 00초 부터 23시 59분 59초까지의 모든 경우는 86,400가지 밖에 존재하지 않기 때문이다. 다시 말해 경우의 수가 100,000개도 되지 않으므로 파이썬에서 문자열 연산을 이용해 3이 시각에 포함되어 있는지 확인해도 시간 제한 2초 안에 문재를 해결할 수 있다.

따라서 단순히 시각을 1씩 증가시키면서 3이 하나라도 포함되어 잇는지 확인하면 될 것이다.

전체 시, 분, 초에 대한 경우의 수는 24 x 60 x 60이며 3중 반복문을 이용해 계산할 수 있다.

이러한 유형은 완전 탐색(Brute Forcing) 유형으로 분류되기도 한다. 완전 탐색 알고리즘은 가능한 경우의 수를 모두 검사해보는 탐색 방법이다. 완전 탐색 문제 또한 구현이 중요한 대표적인 문제 유형인데, 일반적으로 완전 탐색 알고리즘은 비효율적인 시간 복잡도를 가지고 있으므로, 데이터 개수가 큰 경우에 정상적으로 동작하지 않을 수 있다. 그래서 일반적으로 알고리즘 문제를 풀 때는 확인(탐색) 해야 할 전체 데이터의 개수가 100만 개 이하일 때 완전 탐색을 사용하면 적절하다.

다음 소스코드에서는 매 시각을 문자열로 바꾼 다음 문자열에 '3'이 포함됐는지 검사한다. 다시 말해 00시 00분 00초부터 23시 59분 59초 까지 1초씩 늘리며 시, 분, 초를 문자열 자료형으로 변환하여 합친다. 예를 들어 03시 20분 35초일 때를 확인한다면, 이를 '032035' 로 만들어서 '3' 이 '032035' 에 포함되어 있는지를 체크하는 방식을 이용한다.

답안 예시

# 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)

구현 문제 유형은 앞에서 공부했던 그리디 알고리즘 문제 유형과 비교했을 때 큰 차이가 느껴지지 않을 수 있다. 애초에 구현 유형과 그리디 유형은 별개가 아니라 하나의 문제에 구현 유형과 그리디 유형이 함께 포함된 형태로 출제되는 경우가 많기 때문이다. 즉 하나의 문제에는 여러 개의 문제 유형이 포함되는 경우가 많다.

 

---

본 포스팅은 ‘이것이 코딩 테스트다 with 파이썬’을 읽고 공부한 내용을 바탕으로 작성하였습니다.

 

 

 

작성자 : 엄코딩 eomcoding