현재까지 나온 알파벳의 개수를 저장하는 배열 int[26] checked
을 만들고, 한 단어를 확인할 때마다 이 단어에 나오는 알파벳을 추가해준다
예를들어 abc
라는 단어가 있을 때, checked[0]++, check[1]++, check[2]++
과 같은 과정을 거치고, 한 단어를 추가해 문장을 만들 때마다 checked[]
배열의 모든 값이 0 이상인지 확인한다 (알파벳이 하나 사용될 때마다 +1씩 되므로 모든 값이 0이상이라는 말은 알파벳을 모두 사용했다는 뜻이다)
문장을 만드는 함수에서 idx번 째
단어를 선택해서 문장을 만드는 경우와, 이를 선택하지 않고 문장을 만드는 경우 모두를 탐색해야 한다
private static void makeSentence (int idx) {
if (idx==N) return;
for (int i=0; i<str[idx].length(); i++) {
char c=str[idx].charAt(i);
checked[c-'a']++;
}
if (checkAlpa()) cnt++;
makeSentence (idx+1);
for (int i=0; i<str[idx].length(); i++) {
char c=str[idx].charAt(i);
checked[c-'a']--;
}
makeSentence (idx+1);
}
abcdefghijklmnopqrstuvwxyz
a
b
c
d
e
... 와 같이 단어가 주어졌을 때, 첫 번째 단어만 가지고 문장을 만들었을 경우에도 모든 알파벳을 포함하는데 계속 남은 단어를 추가하면서 문장을 만들고 다시 모든 알파벳이 포함되었는지 확인하는 작업을 거침cnt
로 관리하기 위해 단어가 주어질 때 알파벳을 추가하고 삭제하는 함수를 따로 만듦cnt==26
이 되었을 때, 아직 확인해보지 않은 남은 단어들을 굳이 확인하지 않고, 남은 단어를 통해 만들 수 있는 부분집합의 개수를 결과 값에 더해준다 if (cnt==26) {
ret+=1 << (N-idx);
return ;
}
package recursion;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class BOJ9997 {
static int N;
static String[] str;
static int[] checked=new int[26];
static int cnt,ret;
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader (new InputStreamReader (System.in));
N=Integer.parseInt(br.readLine());
str=new String[N];
for (int i=0; i<N; i++)
str[i]=br.readLine();
makeSentence (0);
System.out.println(ret);
}
private static void makeSentence (int idx) {
if (cnt==26) {
ret+=1 << (N-idx);
return ;
}
if (idx==N) return;
for (int i=0; i<str[idx].length(); i++) {
char c=str[idx].charAt(i);
add(c);
}
makeSentence (idx+1);
for (int i=0; i<str[idx].length(); i++) {
char c=str[idx].charAt(i);
remove(c);
}
makeSentence (idx+1);
}
private static void add (char c) {
if (++checked[c-'a']==1) cnt++;
}
private static void remove (char c) {
if (--checked[c-'a']==0) cnt--;
}
}
ALPHA
를 만들어두고 이와 같은 상황일 때 모든 알파벳이 사용된 것이다(1 << 26) = 0000 0100 0000 0000 0000 0000 0000 0000
int ALPHA = (1 << 26) - 1 = 0000 0011 1111 1111 1111 1111 1111 1111
words[]
라는 배열을 선언하고, 여기에는 각 단어의 비트마스크를 담는다abc와 같은 경우 0111이 저장
String str=br.readLine();
for (int j=0; j<str.length(); j++) {
words[i] |= 1<<str.charAt(j)-'a';
}
mask
에서 다음 단어를 선택할 경우, 선택하지 않을 경우 2가지를 살펴본다 private static void dfs (int idx, int mask) {
if (idx==N-1) {
if (mask==ALPHA) ret++;
return ;
}
dfs (idx+1, mask | words[idx+1]);
dfs (idx+1, mask);
}
package recursion;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class BOJ9997_2 {
static int N;
static int ret;
static int[] words; // 각 단어의 비트마스크가 들어있는 배열
static final int ALPHA = (1<<26)-1;
// 0000 0011 1111 1111 1111 1111 1111 1111
// 모든 알파벳을 사용했을 경우 비트마스크
public static void main(String[] args) throws IOException {
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 str=br.readLine();
for (int j=0; j<str.length(); j++) {
words[i] |= 1<<str.charAt(j)-'a';
}
}
dfs (-1, 0);
System.out.println(ret);
}
private static void dfs (int idx, int mask) {
if (idx==N-1) {
if (mask==ALPHA)
ret ++;
return ;
}
dfs (idx+1, mask | words[idx+1]);
dfs (idx+1, mask);
}
}
비트 마스크를 잘 사용 안 했기 때문에 시간 초과 문제를 해결하지 못하고 다른 사람 풀이를 참고했다
비트 마스크를 이용한 문제를 더 풀어보자