🖊️ 문제

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

---

🖊️ 생각

1. 처음에는 쌩 노가다로,
   a~b 사이의 모든 숫자를string 으로 변환한 뒤, 4와 7로만 이루어져 있는지 판별했다.
   -> 당연히 시간초과

2. DFS를 이용해서 재귀적으로 10씩 곱해가며, 4와 7로만 이루어져 있는 애들을 vector에 넣어줌
   -> 메모리 초과

간단 코드

void DFS(int cur)
{
	if (cur > 1'000'000'000) 
		return;
	vec.push_back(cur);
	DFS(cur * 10 + 4);
	DFS(cur * 10 + 7);
}


int main()
{
	...
    
	DFS(4);
	DFS(7);

	int answer = 0;
	for (int i = a; i <= b; i++) {
		if (find(vec.begin(), vec.end(), i) != vec.end())
			answer++;
	}
	
	cout << answer << endl;
}

3. 간단한 bfs 로 변경 -> 함수 호출 스택 줄이기

4. 4와 7로만 이루어져 있는지 확인하는 과정에서 a ~ b 사이 값인지 확인
   ->vector에 넣어주고, find하는 불필요한 연산을 줄임

---

🖊️ 풀이

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

vector<long long> vec;
queue<long long> q;

int main()
{
	long long a, b;
	cin >> a >> b;

	int answer = 0;
	
	q.push(4);
	q.push(7);
	while (!q.empty()) {
		long long cur = q.front();
		if (cur > b)
			break;
		if (cur >= a && cur <= b)
			answer++;
		q.pop();
		q.push(cur * 10 + 4);
		q.push(cur * 10 + 7);
	}
	
	cout << answer << endl;
}

---

🖊️ 고칠점

1. 적절한 자료형 사용
   범위는 int 안에서 해결이 가능하지만,
   10씩 곱하다보면 int를 벗어날 수 있으므로 long long을 사용함
   이러한 것들을 문제만 보고 잘 사용할 줄 알아야 함
   (난 디버깅해보고 알았음 ㅠㅠ)

2. 불필요한 과정 줄이기
   굳이 컨테이너에 넣고, 다시 찾는 과정은 메모리상으로도, 시간 상으로도 굉장한 오버헤드.
   줄일 수 있는 연산들은 시간을 줄여보자.