들어가며
https://www.acmicpc.net/problem/1062
문제 이해는 직관적으로 가능하다. antaXXXXtica로 이루어지는 단어가 N개 주어졌을때, K개의 영어 소문자 단어를 아는 학생들이 N개의 단어들을 읽었을때 최대 몇개를 읽을 수 있는가를 출력하는 문제이다. 즉 K개의 영단어의 조합을 뽑아내서 그중 가장 많이 읽을 수 있는 케이스를 출력하면 된다.
본문으로
조합이기 때문에 DFS재귀적으로 원상복귀시키며 탐색하며 최댓값을 갱신시키는 방식으로 다음 풀이를 제출했다.
public class Main {
static int N, K, ret;
static Set<Character> set;
static List<String> words;
static void go(Set<Character> set, int idx) {
if (set.size() == K) {
if (!set.contains('a') || !set.contains('n') || !set.contains('t') || !set.contains('i') || !set.contains(
'c')) {
return;
}
ret = Math.max(ret, readWord(set));
return;
}
for (int i = idx; i < 26; i++) {
set.add((char) (i + 97));
go(set, i + 1);
set.remove((char) (i + 97));
}
}
static int readWord(Set<Character> set) {
int cnt = 0;
for (int i = 0; i < words.size(); i++) {
boolean isContain = true;
for (int j = 0; j < words.get(i).length(); j++) {
if (!set.contains(words.get(i).charAt(j))) {
isContain = false;
break;
}
}
if (isContain) {
cnt++;
}
}
return cnt;
}
public static void main(String[] args) throws Exception {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken()); // 0~25
words = new ArrayList<>();
set = new HashSet<>();
for (int i = 0; i < N; i++) {
words.add(bf.readLine());
}
ret = 0;
go(set, 0);
System.out.println(ret);
}
}
시간 복잡도가 걱정되며 풀었는데.. 2의 26승이라.. 정말 간당간당하게 통과한 느낌이다.
풀면서 결국 해당 단어를 포함시키나 안시키나만 처리하면 되기 때문에 0과 1로 나타내어 비트마스킹으로 풀 수 있겠다.. 라는 생각은 했는데, 구현 흐름 자체가 떠오르지 않았다.ㅜ 그래서 다른분들 코드를 많이 참고해서 아래와 같은 코드를 작성했다.
public class Main {
static int N, M;
static int[] words;
static String s;
static int count(int mask) {
int cnt = 0;
for (int i = 0; i < N; i++) {
int word = words[i];
if ((word & mask) == word) {
cnt++;
}
}
return cnt;
}
static int go(int idx, int k, int mask) {
if (k < 0) {
return 0;
}
if (idx == 26) {
return count(mask);
}
int ret = go(idx + 1, k - 1, mask | (1 << idx)); // 현재 글자를 배우고 넘어가기
if (idx != 'a' - 'a' && idx != 'n' - 'a' && idx != 't' - 'a' && idx != 'i' - 'a'
&& idx != 'c' - 'a') { // 해당 글자들은 무조건 배워야함
ret = Math.max(ret, go(idx + 1, k, mask)); // 현재 글자를 안 배우고 넘어가기
}
return ret;
}
public static void main(String[] args) throws Exception {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
words = new int[51];
for (int i = 0; i < N; i++) {
s = bf.readLine();
for (int j = 0; j < s.length(); j++) {
words[i] |= (1 << s.charAt(j) - 'a');
}
}
System.out.println(go(0, M, 0));
}
}핵심은 아래 로직이다. 비트마스킹은로 풀더라도 a ,b, c, d... 순서대로 하나씩 배우고 안배우며.. 모든 경우의 수를 탐색하는 로직을 아래와 같이 구성했다... 특히 현재 글자를 배우고 넘어가는 부분은 mask | ( 1 << idx)); 로 OR 연산자로 해당 비트를 켜주는 방식이 너무 깔끔하다...! 배웠으면 k를 -1 시키며 재귀적으로 탐색을 진행한다. (k < 0)이면 바로 return하기에 더 많이 배우는 경우도 가지치기 할 수 있다. 결국 모든 알파벳을 다 돌았을때 단어를 읽을 수 있나 count해준다.
static int go(int idx, int k, int mask) {
if (k < 0) {
return 0;
}
if (idx == 26) {
return count(mask);
}
int ret = go(idx + 1, k - 1, mask | (1 << idx)); // 현재 글자를 배우고 넘어가기
if (idx != 'a' - 'a' && idx != 'n' - 'a' && idx != 't' - 'a' && idx != 'i' - 'a'
&& idx != 'c' - 'a') { // 해당 글자들은 무조건 배워야함
ret = Math.max(ret, go(idx + 1, k, mask)); // 현재 글자를 안 배우고 넘어가기
}
return ret;
}아래 사진을 보면 위의 제출은 비트마스킹 풀이의 제출이고, 아래는 처음의 Set을 이용해 재귀적으로 탐색한 제출이다. 공간복잡도랑 시간복잡도의 차이가 이거이거 뭐... 2배도 아니고 엄청 차이난다! 재귀적으로 돌며 Set 자료구조에 그때그때 add, remove하며 Chracter 객체를 만들고~ 삭제해서 메모리가 매우 많이 나왔다. 하지만 비트 마스킹 풀이는 사실상 int배열 하나만 사용하기에 CPU cache hit이 매우 높다. 그래서 메모리가 크기가 차이가 많이 나나보다.
마무리하며
모든 조합을 뽑아내기 + 백트래킹 문제를 보면 항상 재귀적 풀이가 먼저 떠오르는데, 그냥 시간복잡도 신경 안쓰고 푸는거는 사실 이제 그렇게 어렵지 않다...
하지만 이렇게 비트마스킹 기법을 추가하면 시간복잡도나 공간복잡도 측면에서 몇 배 이상의 이득을 보는데,,, 제한이 심한 문제에서는 꼭 필요한 풀이가 아닌가싶다... 근데 로직 구현자체가 너무 어렵다.. 연습하자!! 0, 1의 경우의 수가 있는 문제라면 비트마스킹 고려해보자!!!