[이코테][구현]시각

문제

Chapter 04 구현 中 4-2. 시각
난이도 ★☆☆, 풀이시간 15분, 시간제한 2초, 메모리 제한 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이 하나라도 포함되는 모든 경우의 수를 출력한다.

입력 예시                                                  출력 예시

5

11475

 

---

문제 풀이 과정

체감 난이도 ★★☆, 소요시간: 20분
어려웠던 부분: 문제 이해, 문자열 변환

 이 문제는 문제 이해에서 다소 난항을 겪었다. 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수인데 00시 02분 55초는 3이 하나도 포함되어있지 않아 세면 안되는 시각이라고 한다. 하지만 02분 55초 안에는 1분 33초처럼 3이 포함되는 시각이 존재하지 않는가?라는 생각이 들었다. 하지만 이것은 문제 이해의 오류였다.

문제의 궁극적인 요구 조건은 N, 즉 시간이므로 그 안에 존재하는 시각의 종류를 예시로 든 거지, 최종 목적지를 가리키는 것이 아니었다는 것이다. 되돌이켜보니 정말 부끄러운 일이었다.

로직

갈피를 잡은 후 분과 초는 59로 단위가 고정되어 있기 때문에 시간만 입력받아 3중 반복문을 돌려 3이 포함된 경우를 카운팅해주는 로직을 고안하였다. 하지만 단순히 정수형을 취급한다고 생각해 작성한 if문에서 문제가 생겼다. TypeError: argument of type 'int' is not iterable 에러가 난 것이다.

TypeError 발생

반복문을 돌릴 때 사용하는 i, j, m은 iterable의 반복 가능한 객체이다. 어느 하나의 객체에서 자료를 반복적으로 꺼내올 수 있는 리스트, 튜플, 딕셔너리, set, string, byte, range가 이에 해당하는데 int형으로 받아준 것이 문제가 되었다.

코드

#실패 코드
clock = int(input()) #시각 입력받기

count = 0 #3이 들어가는 시각의 개수를 입력받을 변수 초기화

for i in range(clock+1): #시분초 나누어 3중반복문
    for j in range(60):
        for m in range(60):
            if 3 in i+j+m: #3이 포함된 경우
                count += 1
print(count)

 

답안 예시

해설 & 오답노트

 이러한 유형은 완전 탐색 유형(Brute Forcing)으로 분류되기도 한다. 완전 탐색 알고리즘은 가능한 경우의 수를 모두 검사해보는 탐색 방법이다.  일반적인 브루트 포스 알고리즘은 비효율적인 시간 복잡도를 지니기 때문에 전체 데이터 개수가 100만 개 이하일 때 사용하면 적절하다.

이전 풀이에서 오류를 범했던 int형 처리 부분을 해결하기 위해 매 시각을 문자열로 바꾼 다음 문자열에 '3'이 포함되었는지 검사한다. 즉, 가능한 경우의 수를 1초씩 늘려가며 시, 분, 초를 문자열 자료형으로 변환한 다음 합치는 것이다. 예를 들어 03시 20분 35초일 때, '032035'로 변환한 다음 '3'이 이에 포함되어 있는지 체크한다

코드(책의 예시)

'''
시각(백준 18312)
1. 시각 입력받기
2. 시/분/초 나누어 3중 반복문 돌리기
3. 3이 포함된 경우 count++
'''

clock = int(input()) #시각 입력받기

count = 0 #3이 들어가는 시각의 개수를 입력받을 변수 초기화

for i in range(clock+1): #시분초 나누어 3중반복문
    for j in range(60):
        for m in range(60):
            if '3' in str(i) + str(j) + str(m): #3이 포함된 경우
                count += 1
print(count)

 

총평

수행 평가도: ★★☆
배운 점&느낀점: 자료형 구분, 완전 탐색 유형, 문제 서칭 

 여태까지 해결했던 문제 중 선형적인 알고리즘을 많이 사용했었는데, 그 중 하나가 완전 탐색 유형에 해당된다는 것을 알게 되었다. 자료형에서 막힌 케이스를 보고 자료형 분류의 중요성을 또 한번 깨닫게 되었다. 부족한 부분을 깨닫게 되니 스스로 백준의 비슷한 문제들을 찾아보게 되었다. 앞으로 비슷한 유형의 문제들을 풀어보며 체화시키는 연습을 꾸준히 해 나가야겠다고 느꼈다.