[CH4 구현] 아이디어를 코드를 바꾸는 구현 3

예제 4-2) 시각

• 정수 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

 

---

풀이)

• 이 문제는 모든 시가의 경우를 문자열로 보고, 하나씩 모두 세서 쉽게 풀 수 있는 문제이다
• 왜냐면 하루는 86,400초로, 00시 00분 00초부터 23시 59분 59초까지의 모든 경우는 86,400가지밖에 존재하지 않기 때문이다 -> 24*60*60=86,400
• 따라서 모든 경우의 수가 100,000개도 되지 않기 때문에 문자열 연산을 통해 3이 포함되어 있는지 확인해서 풀면 2초 안에 해결이 가능하다
• 따라서 단순히 시각을 1씩 증가시키면서 3이 하나라도 포함되어 있는지 확인하면 될 것이다 -> 3중 반복문 사용
• 이러한 유형은 완전 탐색(Bruce Forcing) 유형으로 분류되기도 한다
• 완전 탐색 알고리즘은 가능한 경우의 수를 모두 검사해보는 탐색 방법이다
• 완전 탐색 문제 또한 구현이 중요한 대표적인 문제 유형인데, 일반적으로 완전 탐색 알고리즘은 비효율적인 시간 복잡도를 가지고 있어서 알고리즘 문제를 풀 때는 확인(탐색)해야 할 전체 데이터의 개수가 100만 개 이하일 때 완전 탐색을 사용하면 적절하다

 

파이썬 코드)

#n을 입력받기
n=int(input())

count=0
for i in range(n+1):
    for j in range(60):
        for k in range(60):
            #매 시각 안에 3이 포함되어 있으면 count++
            if '3' in str(i) + str(j) + str(k):
                count +=1

print(count)

와~ 파이썬 코드 타이어보다 싸다(?)

그만큼 쉽다는 거지

c++ 코드)

안되던 코드

(트러블슈팅)

이거 왜 안되는지 고민중,,,

와 이제 알았다

저기 60까지 돌면안됨...

시간이 00:59:59니까 분, 초가 59일떄까지만 세야댐

자꾸 결과가 더 나와서 왜지 했는데 나는야 똥멍청이,,,쥬륵

급하게 풀어서 생각을 못했나부다,,ㅠ

 

 

C++) 요 아래가 맞게 구현한 코드

#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;

int main()
{
    int n;
    int count=0;
    string time;
    
    cin>>n; //시간 n 입력받기
    
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<60;j++)
        {
            for(int k=0;k<60;k++)
            {
                time=to_string(i)+to_string(j)+to_string(k);
                if(time.find('3') != string::npos)
                {
                    count++;
                }
            }
        }
    }
    cout<<count;
    return 0;
}

암튼 겨우 끝,,,^^