[C++/BOJ] 백준 18312 시각(완전탐색)

https://github.com/tony9402/baekjoon/tree/main/brute_force

GitHub - tony9402/baekjoon: 코딩테스트 대비 문제집(Baekjoon Online Judge)

 

저번 포스팅에 이어 코테를 대비해 완탐 문제들을 풀고있다. 

 

 

 

 

https://www.acmicpc.net/problem/18312

18312번: 시각

 

 

 

 

 

설마 3중 for문?

 

 

3중 for문으로 만들어서 해보았다.

문제에 나와있는 예시는 답이 잘 나오지만 제출해보면 틀렸습니다가 뜬다.

 

<틀린 코드>

#include<iostream>
#include<string>
using namespace std;
int n,k;
int cnt;
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k;
	bool isk;
	for (int i = 0; i <=n; i++) {
		for (int j = 0; j <= 59; j++) {
			for (int u = 0; u <= 59; u++) {
				isk = 0;
				string tmph = to_string(i);
				int sizeh = tmph.size();
				for (int z = 0; z < sizeh; z++) {
					if (tmph[z] - '0' == k) {
						isk = 1;
					}
				}
				string tmpm = to_string(j);
				int sizem = tmpm.size();
				for (int z = 0; z < sizem; z++) {
					if (tmpm[z] - '0' == k) {
						isk = 1;
					}
				}
				string tmps = to_string(u);
				int sizes = tmps.size();
				for (int z = 0; z < sizes; z++) {
					if (tmps[z] - '0' == k) {
							isk = 1;
					}
				}
				if (isk == 1) cnt++;
			}
		}
	}
	cout << cnt;
}

 

 

 

몇번 수정해보다가 안되서 백준의 질문과 다른 사람의 코드를 찾아보았다. 

 

 

https://jerimo.github.io/boj/boj-18312/

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

https://www.acmicpc.net/board/view/60101

글 읽기 - 왜 틀린지 아시는분 있나요?

 

십의자리의 0의경우 for문에서 05처럼 0을 붙여주는 것이 아니므로 count가 되지않는다!!

이 생각을 못하고 있었다!

 

그리고 더 쉽게 풀수있는 코드를 발견해서 적용하였다. 

 

 

 

 

#include<iostream>
#include<string>
using namespace std;
int n,k;
int cnt;
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k;
	string str;
	for (int i = 0; i <=n; i++) {
		for (int j = 0; j <= 59; j++) {
			for (int u = 0; u <= 59; u++) {
				if (i / 10 == 0) { // 한글자일경우 앞에 0을 붙여준다.
					str += "0";
				}
				str += to_string(i);
				if (j / 10 == 0) { // 한글자일경우 앞에 0을 붙여준다.
					str += "0";
				}
				str += to_string(j);
				if (u / 10 == 0) { // 한글자일경우 앞에 0을 붙여준다.
					str += "0";
				}
				str += to_string(u);
				
				if (str.find(to_string(k))!= -1) cnt++;
				str.clear();
			}
			
		}
	}
	cout << cnt;
}

 

 

새롭게 알게된 string 관련 함수 => find함수, clear함수

 

1 ) str.find ("a") -> str에서 a를 찾아 위치를 반환한다. 없다면 -1을 반환한다.

 

2) str.clear -> str을 비운다.

 

그리고 ! string은 += 을 이용해서 문자를 붙이고 뗄수있다. 

 

 

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

 

 

이 문제만해도 3중 for문이면 O(n^3)이다.

 

해당 문제가 완전탐색이라는 것을 알고 풀어서 풀수있는거지 모르고 푼다면 겁도없이 3중 for문을 쓰지는 않을것이다. n의 개수를 확인하고 시간복잡도를 생각해서 완탐을 써야한다는 것을 알 수 있었다.