1062번: 가르침

먼저 재귀로 풀었다.

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

int alpha[26];
int nam[5] = { 'a' - 'a','n' - 'a','t' - 'a','i' - 'a','c' - 'a' };

int ans = 0;
int n, k;
vector<string> b;
vector<int> al;
int check() {
	int sum = 0;
	int b_size = b.size();
	for (int i = 0; i < b_size; i++) {
		int bb_size = b[i].size();
		bool ok = true;
		for (int j = 0; j < bb_size; j++) {
			if (alpha[b[i][j] - 'a'] == false) {
				ok = false;
				break;
			}
		}
		if (ok) {
			sum++;
		}
	}
	return sum;
}
void go(int index) {
	if (index >= k) {
		int temp = check();
		if (ans < temp) {
			ans = temp;
		}
		return;
	}
	int al_size = al.size();
	for (int i = 0; i < al_size; i++) {
		if (alpha[al[i]]) continue;
		alpha[al[i]] = true;
		go(index + 1);
		alpha[al[i]] = false;
	}
}

int main() {
	std::chrono::system_clock::time_point start = std::chrono::system_clock::now();
	cin >> n >> k;
	vector<string> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	b = a;
	k -= 5;

	if (k < 0) {
		cout << 0 << '\n';
		return 0;
	}
	for (int i = 0; i < 5; i++) {
		alpha[nam[i]] = true;
	}
	int b_size = b.size();

	for (int i = 0; i < b_size; i++) {
		int bb_size = b[i].size();
		for (int j = 0; j < bb_size; j++) {
			if (alpha[b[i][j] - 'a'] == false) {
				al.push_back(b[i][j] - 'a');
			}
		}
	}

	go(0);

	cout << ans << '\n';
	std::chrono::duration<double> sec = std::chrono::system_clock::now() - start;
	cout << sec.count() * 1000 << "ms" << endl;
	cout << endl;
	return 0;
}

20.9504ms  로 시간초과 났음

 

int check() {
	int sum = 0;
	int b_size = b.size();
	for (int i = 0; i < b_size; i++) {
		int bb_size = b[i].size();
		bool ok = true;
		for (int j = 0; j < bb_size; j++) {
			if (alpha[b[i][j] - 'a'] == false) {
				ok = false;
				break;
			}
		}
		if (ok) {
			sum++;
		}
	}
	return sum;
}

이 부분은 O(단어 갯수* 단어 길이) 만큼의 시간복잡도가 생성된다.

-> 문제에서는 단어안의 알파벳의 갯수, 알파벳의 순서는 중요하지 않고

단어에 속해있는 알파벳이 무엇인지가 중요함으로 비트 마스크를 이용해 풀면 

O(단어갯수) 만큼의 시간복잡도로 시간을 단축 시킬수있다.