[알고리즘]구현_시각(파이썬 포함연산자 in, not in/숫자를 문자로 바꾸는 메소드 str()과 연결연산자 +)

['시각' 문제 설명]

-난이도 : ★☆☆

-풀이시간 : 15분 

-시간 제한 : 2초

-메모리 제한 : 128MB

-출처 : 이것이 코딩테스트다 (p.113)

 

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

 

 

-입력예시1

5

-출력예시1

11475

 

['시각' 답안1]

#n을 입력받는다
n = int(input())

#n이 5라면 00시 00분 00초 ~ 05시 59분 59초 까지 검사

count = 0
for i in range(n+1) :
    for j in range(60) :
        for k in range(60) :
            #매 시각 안에 '3'이 포함되어 있다면 카운트 증가.
            #3:5:25라면 '3525'중 3이 포함되어 있으므로 count증가
            if '3' in str(i)+str(j)+str(k) :
                count = count+1

print(count)

 

[설명]

-이러한 유형은 완전탐색 유형으로 분류된다.

'완전 탐색 알고리즘'이란 가능한 경우의 수를 모두 검사해보는 탐색 방법이다

 

-완전 탐색 문제 또한 구현이 중요한 대표적인 문제 유형인데, 일반적으로 완전 탐색 알고리즘은 비효율적인 시간 복잡도를 가지고 있으므로 데이터 개수가 큰 경우네 정상적으로 동작하지 않을 수 있다.

그래서 데이터 개수가 100만개 이하일 때 완전탐색을 사용하면 적절하다.

 

-이 문제는 매 시각을 문자열로 바꾼 다음 문자열에 '3'이 포함되었는지 검사한다.

ex) 03시20분35초라면 '032035'에 3이 포함되어 있는지 체크하는 방식을 사용한다.

[파이썬]

01.포함연산자 in, not in

if 'p' in 'python': 
    print(True) 
else: 
    print(False)

└문자열에 해당문자가 있는 지 검사하여 true 혹은 false를 반환한다.

└위 예제의 경우 p가 python내에 있으므로 True를 출력한다.

 

 

02.숫자를 문자로 바꾸는 메소드 str()과 연결연산자 +

ex) str(3) + str(5) = '35' 가 된다.