ray

ray

매일의 HIGHLIGHT를 찾아서 ✨

[백준] 18312 시각 (C++)

Posted on Feb 5, 2021 #구현   #완전 탐색(Brute Forcing)   #Algorithm  

18312 | 시각

🙋‍♀️ 문제

정수 N과 K가 입력되었을 때 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 K가 하나라도 포함되는 모든 시각을 세는 프로그램을 작성하시오. 시각을 셀 때는 디지털 시계를 기준으로, 초 단위로만 시각을 구분한다.

예를 들어 K=3일 때, 다음의 시각들은 3이 하나 이상 포함되어 있으므로 세어야 하는 시각의 대표적인 예시이다.

  • 23시 00분 00초
  • 07시 08분 33초

🙌 입출력

첫째 줄에 정수 N과 K가 공백을 기준으로 구분되어 주어진다. (0≤N≤23, 0≤K≤9)

00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 K가 하나라도 포함되는 시각들의 수를 출력한다.

🙋‍♂️ 예제 입출력

5 3

11475

🚀 코드

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
	int n, k = 0;
	cin >> n >> k;
	int cnt = 0;
	string s;

	for (int i = 0; i <= n; i++) {
		for (int j = 0; j < 60; j++) {
			for (int l = 0; l < 60; l++) {
				if (i / 10 == 0) {
					s += "0";
				}
				s += to_string(i);
				if (j / 10 == 0) {
					s += "0";
				}
				s += to_string(j);
				if (l / 10 == 0) {
					s += "0";
				}
				s += to_string(l);
				if (s.find(to_string(k)) != -1) {
					cnt++;
				}
				s.clear();
			}
		}
	}
	std::cout << cnt;

	return 0;
}

🌠 메모

이러한 문제는 브루트포스로 불리는 완전 탐색 유형으로 분류되기도 한다.

일반적으로 완전 탐색 알고리즘은 비효율적인 시간 복잡도를 가지고 있으므로 데이터 개수가 큰 경우에는 제대로 동작하지 않을 수 있다. 따라서 전체 데이터 개수가 100만개 이하일때만 완전 탐색을 사용하도록 하자.

위의 문제만 봐도 시간 복잡도가 O(n^3)이다.

int형 정수를 string으로 바꾸기 위해 to_string()함수를 사용했다. 또한 string.find()와 같이 다양한 string 내장 함수를 사용하였는데, 이는 나중에 필요하거나 중요한 함수 위주로 정리해 볼 예정이다.

학부 수업을 들을때는 대부분의 함수를 구현해서 사용하느라 라이브러리를 문제 풀이에 사용하는 경우가 드물었는데, 실제 코딩 테스트를 준비해보니 주요 함수들의 사용법들은 숙지해 두는 편이 좋은 것 같다.

! 주의할 점

시, 분, 초가 한 자리 수 일때 앞에 “0”을 추가해 줘야 한다.

  • 0시 0분 0초 (x)
  • 00시 00분 00초 (o)


# 카테고리