문제
N개의 단어가 주어질 때, 일부 단어들을 선택하여 a-z 26개 알파벳을 모두 포함하는 경우의 수를 구하라.
입력
첫째 줄에 N, 이후 N줄에 단어가 하나씩 주어진다.
출력
알파벳 26개를 모두 포함하는 부분집합의 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
2 abcdefghijklm nopqrstuvwxyz | 1 |
풀이
각 단어를 26비트 마스크로 표현하고, DFS로 모든 부분집합을 탐색하여 OR 결과가 전체 알파벳인 경우를 센다.
- 각 단어에 포함된 알파벳을 비트마스크로 변환한다
- DFS에서 각 단어를 선택하거나 선택하지 않는 두 가지 분기를 탐색한다
- 마지막 단어까지 처리 후 마스크가
(1<<26)-1이면 카운트를 증가시킨다
핵심 아이디어: 비트 OR 연산으로 선택된 단어들의 알파벳 합집합을 효율적으로 관리하며, 2^N 부분집합을 탐색한다.
코드
package day549;
import java.io.*;
public class Day517BOJ9997폰트 {
static final int ALPHA = (1 << 26) - 1;
static int N, ans;
static int[] words;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
words = new int[N];
for (int i = 0; i < N; i++) {
String[] input = br.readLine().split("");
for (int j = 0; j < input.length; j++) {
words[i] |= 1 << input[j].charAt(0) - 'a';
}
}
dfs(-1, 0);
System.out.println(ans);
}
static void dfs(int count, int mask) {
if (count == N - 1) {
if (mask == ALPHA) {
ans++;
}
} else {
dfs(count + 1, mask | words[count + 1]);
dfs(count + 1, mask);
}
}
}복잡도
- 시간: O(2^N)
- 공간: O(N)