👑1062 가르침. 개선할 부분

잘못된 점 241107

: 백트래킹에서 조건부로 사용되는 갱신용 변수는 전역으로 사용하지 말고,
인자로 보내서 처리하자.

• 카운팅하는 부분을 매번 하는 것이 아니라. 조건식을 통해 해야 한다.
  

---

최근 풀이 240127

: 조합으로 하려고 했는데, 뭐가 문제일까...
-> 나는 21개 중에서 k - 5개만큼 조합을 구하려고 했는데,,,,
이렇게 되면 시간 복잡도 엄청 커짐.

https://velog.io/@ssssujini99/%EB%B0%B1%EC%A4%80C1062%EB%B2%88%EA%B0%80%EB%A5%B4%EC%B9%A8

• 참고 사이트이고, 문자 입력받을 때 , a n t i c 를 제외한 문자를 얻음.
  그러니까, 여기서, 빨간색 부분에 대한 조합을 해야함.
  즉, rhelo 를 가지고 조합을 하는 방향으로 나아가야 함...
  5 개 중에서 k - 5 만큼의 조합을 진행하고, 여기서 k - 5 는 1임.
  조합을 위해서는 반드시 5개만 큼 중 1개를 선택해야 하니까,
  vector arr[5] = { 0,0,0,0,1 } 놓고, sort 까지 한 상태에서 조합 진행하자.

#include <chrono>  // std::chrono::miliseconds
#include <iostream>
#include <mutex>
#include <queue>
#include <string>
#include <thread>
#include <vector>
using namespace std;
#include <condition_variable>
#include <shared_mutex>

#include <unordered_map>
#include <algorithm>


int main()
{
	// a n t a t i c a 
	// a n t i c -> 여기 5가지는 무조건 알아야 함.

	// 26 - 5 중 21개에서 ( k - 5 ) 만큼의 조합을 진행해야 함.

	// k가 6 이라면 21개의 알파벳중에서 1개를 선택해서 조합

	// 5개 글자는 무조건적으로 알아야만 
	// 단어를 읽을 수 있음. 

	// antatica 입력이 최소한의 단어배열리고

	// k가 5 미만이면 0출력 끝.

	// b x d e f g h j k 

	int n, k;
	cin >> n >> k;

	int arr[26] = { 0, };
	

	if (k < 5)
	{
		cout << 0;
		return 0;
	}
	else
	{
		vector<string> word(n);

		for (int i = 0; i < n; ++i)
		{
			cin >> word[i];
		}


		// a n t i c 를 확보한 상태에서 
		// 21 개 중에서 조합을 돌리고 싶음. 
		// b, d , e, f, g, h, j, k ,l ,m , o, p, 
		// q, r, s, u ,v, w, x, y ,z 


		// 어떻게 할 거냐면 벡터에 넣고, 
		// next_permutation 돌리면서 
		// k - 5 만큼을 for문에서 가장 앞에 있는 걸로 
		vector<char> c = { 'b', 'd' ,
			'e', 'f', 'g', 'h', 'j', 'k' ,'l'
			,'m' , 'o', 'p',  'q', 'r', 's', 'u'
			,'v', 'w', 'x', 'y' ,'z' };
		sort(c.begin(), c.end());
		int cnt = k - 5;
		//unordered_map<char, bool> check;
		//check['a'] = true;
		//check['n'] = true;
		//check['t'] = true;
		//check['i'] = true;
		//check['c'] = true;

		vector<bool> check(26, false);
		check['a' - 'a'] = true;
		check['n' - 'a'] = true;
		check['t' - 'a'] = true;
		check['i' - 'a'] = true;
		check['c' - 'a'] = true;


		int res = 0;

		do
		{
			
			for (int i = 0; i < cnt; ++i)
			{
				check[c[i] - 'a'] = true;		
			}

			int ccnt = 0;

			// 단어 전체 돌리기.
			for (int k = 0; k < word.size(); ++k)
			{
				bool br = false;
				// 단어 한글자씩 확인하기.
				for (int l = 0; l < word[k].size(); ++l)
				{
					if (check[word[k][l] - 'a'] == false)
					{
						br = true;
						break;
					}
				}
				if (br == false)
				{
					++ccnt;
				}
			}

			for (int i = 0; i < cnt; ++i)
			{
				// 원복.
				check[c[i] - 'a'] = false;
			}

			res = max(res, ccnt);

		} while (next_permutation(c.begin(), c.end()));

		cout << res << endl;

	}


}

---

최종 코드

http://boj.kr/223b0a3a54894c7cbd71ab6e56552732

• 풀이 시간 : 220908 18:10 ~ 19:22

🙉개선할 점.

1) 일단은 쉽게 생각해서 접근하자.
2) 시간 복잡도 걸리면, 타이트 하게 접근하고.

• 참고한 블로그 주인장님.
  https://ongveloper.tistory.com/132

-> 느낀점.
: 너무 어렵게 생각했음.
그냥 a n t i c 제외하고 26 - 5 중에서 k - 5 만큼 다 돌린 다음에
string 벡터와 확인하는 식으로 하자.

🙉중요한 부분

3) 조합 안에서 체크 변수 확인하려고 또 26개 돌리면서 확인했는데,
이러지 말고, 이런식으로 확인하자.

• 내용 : 이미 내가 불체크 표시를 했으므로,
  해당 rc , hello, car 에 대한 불변수가 true인지 확인만 하면 됨!

• 개선된 코드
  

• 좋지 못한 , 시간 복잡도 증가하는 코드
  

93퍼에서 틀림.

http://boj.kr/30cc1e4a3ba64679a68e2c5474d5e09f

• 젠장..!
  알고 있었는데 잘못 작성한 부분이 있음.

  문제에서 8과 동일할 수 있다고 한다. 즉
  antatica 가운데에 아무것도 안들어 올수 있다는 소리임.
  근데 나는 알고 있었지만,, 한 부분을 잘못 작성했음.
  
  -잘못 작성한 부분
  
  -antic 총 5개 이므로, k - 5 < 0 으로 해야함.
  아무것도 안들어오면 antatica 즉 5개가 모두 쓰였다는 것이므로...

첫번째 풀이

: 조합으로 하려고 했는데 복잡함...

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

// 1062번. 가르침.
// 19:55 ~ 

int n, k;
bool ccnt[26];

//맵으로 처리하는게 빠를 듯한데? 
vector<char>temp;

map<char, bool>ttemp;

int result = -1;

void combi(vector<string>&v , vector<char>& word , int start)
{
	if (ttemp.size() == k)
	{
		// 여기서 v와 비교 처리하자. 
		bool ccheck = false;
		int cnt = 0;
		for (int a = 0; a < v.size(); ++a)
		{
			int ssize = v[a].size();

			for (auto iter : v[a])
			{
				if (ttemp.find(iter) == ttemp.end())
				{
					ccheck = true;
					break;
				}
			}
			if (ccheck == false)
				++cnt;

		}
		result = max(result, cnt);

		return;
	}


	for (int i = start; i < word.size(); ++i)
	{
		ttemp.insert(make_pair(word[i], true));

		//temp.push_back(word[i]);
		combi(v, word, i + 1);
		//temp.pop_back();

		ttemp.erase(word[i]);

	}

}





int main()
{
	
	cin >> n >> k;

	// 6개의 글자를 가르침.

	

	// anta , tica 
	// a n t i c -> antatica로만 5개가 소요되므로
	// k = 6 - 5 : 1개의 글자만 배울수 있음. 
	// c를 배우면. 
	
	// rc, car 처리가 가능함.

	// a n t i c 를 제외한 글자들 중에서 . 즉, 26 - 5개의 글자중에서
	// k - 5만큼의 조합을 돌려서 
	
	// 체크 변수에서 뽑은 글자의 원소값 을 이용해 true로 설정하고, 
	// 모두다 true 이면 카운팅을 진행
	// 이렇게 진행하면서 카운팅의 최대값을 추출하자. 

	ccnt['a' - 'a'] = true;
	ccnt['n' - 'a'] = true;
	ccnt['t' - 'a'] = true;
	ccnt['i' - 'a'] = true;
	ccnt['c' - 'a'] = true;

	vector<string>v(n);
	for (int i = 0; i < n; ++i)
	{
		cin >> v[i];

		// 앞에 위치함 anta , 뒤에 위치한 tica를 뺌.
		string s1 = v[i].substr(4 , v[i].length() - 8);
		//cout << "output" << endl;
		//cout << s1 << endl;

		v[i] = s1;
		for (auto iter : s1)
		{
			ccnt[iter - 'a'] = true;
		}
		//cout << v[i] << endl;
	}

	vector<char>ww;

	for (int i = 0; i < 26; ++i)
	{
		if (ccnt[i] == true && i != 'a' - 'a'
			&& i != 'n' - 'a' && i != 't' - 'a'
			&& i != 'i' - 'a' && i != 'c' - 'a')
		{
			char c = i + 'a';
			ww.push_back(c);
			cout << c << endl;
		}
	}

	// a n t i c
	if (k - 5 <= 0)
		return 0;

	k -= 5;


	// ww 에 들어있는 원소들 중에서 num를 꺼내 돌리면서 
	// 모두 일치하면 ok.

	// rc    -> r
	// hello -> h e l o  
	// car   -> r
	// 여기 있는 단어들로 벡터에 넣은 다음에 
	// 조합 돌리면서 최대값 확인하기 
	

	combi(v, ww, 0);
	cout << result;
}