1. 문제 분석하기

1.1. 문제 의도

• 순열/조합을 이용한 대표적인 bruteforce 문제입니다.
• 알파벳은 26개, 사용하는 필수 알파벳은 5개, 21개 알파벳 중 K-5개 알파벳을 고르므로 최대 경우의 수는 $_{21}C_{10} = 352,716$입니다.

1.2. 문제 조건

1. $단어의 개수 \leq 50$ , $8 \leq 단어의 길이 \leq 15$이다.
2. 중복되는 단어는 없다.

2. 문제 해결하기

https://velog.io/@embeddedjune/알고리즘-백준-Bruteforce-1062-가르침
에서 한 번 풀었던 문제입니다. 이번에는 조금 더 효율적인 방법으로 구해보겠습니다.

• 우리는 'a', 'c', 'i', 'n', 't' 5글자는 필수적으로 갖고 있어야 합니다.

• 비트마스크를 이용해서 입력받은 단어의 hash값을 계산합니다.

  • 예를 들어, apple 이라는 단어를 입력받았다고 생각합시다.

  • int hash = 0;
    for (int i = 0; i < str.size(); ++i)
        hash |= (1 << (str[i] - 'a'));

  • 알파벳에서 ‘a’를 빼면 n번째 알파벳이라는 걸 구할 수 있고, 해당하는 bit를 or연산으로 set 해주면 해당 단어에 포함된 알파벳들을 알 수 있습니다.

• 'a', 'c', 'i', 'n', 't'에 대한 hash값을 계산합니다.

• 만일 K가 5보다 크거나 같다면 나머지 K-5개 알파벳을 구하러 갑니다.
  아니라면 여기서 바로 예외처리를 해줍니다.

• K-5개 알파벳을 구할 때 재귀(DFS)를 사용합니다.

  • dfs(int len, int alpha, int hash)
  • len은 현재까지 고른 알파벳의 개수,
    alpha는 골라야하는 알파벳의 범위 시작지점,
    hash는 지금까지 만들어진 hash값을 의미합니다.

• K-5개 알파벳을 추가로 다 골랐다면, 모든 단어의 hash값들과 비교하며 OR연산을 했을 때 자기 자신이 나오는 경우를 찾습니다. (= 해당 단어를 읽기 위해서는, 현재 고른 알파벳들이 해당 단어에 모두 포함돼야하며 OR연산은 자기자신이 나오게 됨.)

3. 코드

#include <iostream>
using namespace std;

int N, K, answer, word[51];

void dfs(int len, int alpha, int hash) {
	if (len == K) {		// 알파벳 cnt개 선택 완료
		int result = 0;
		// 현재 hash값으로 읽을 수 있는 word 개수 카운팅.
		for (int i = 0; i < N; ++i)
			if ((hash | word[i]) == hash) result++;
		answer = max(answer, result);
		return;
	}
	// 26개 알파벳 중 k - 5개 알파벳 선택.
	for (int a = alpha; a < 26; ++a) {
		if (hash & (1 << a)) continue;		// 중복검사
		dfs(len + 1, a, hash | (1 << a));	// 다음 알파벳 선택
	}
}

int main() {
    ios::sync_with_stdio(false), cin.tie(NULL);
    cin >> N >> K;
    
    for (int i = 0; i < N; ++i) {
    	string s;
    	cin >> s;
    	// 입력 단어에 대한 hash값 계산 후 저장.
    	for (int j = 0; j < s.size(); ++j)
    		word[i] |= (1 << (s[j] - 'a'));
	}
	// 필수 알파벳 'a', 'c', 'i', 'n', 't'에 대한 hash값 계산.
	int hash = 0;
	string essentialAlpha = "acint";
	for (int i = 0; i < 5; ++i) hash |= (1 << (essentialAlpha[i] - 'a'));
	
	if (K >= 5) dfs(5, 1, hash);
	cout << answer;
}

4. 결과

기존 452ms에서 16ms로 대폭 줄었습니다.