[백준 9997] 폰트

https://www.acmicpc.net/problem/9997

9997번: 폰트

 

테스트 문장에는 알파벳 소문자 26개가 모두 포함되어 있어야 한다.

-> 문장(또는 단어) 어떤 알파벳이 포함되어 있는지 여부를 판단하자!!

 

 

=> 비트마스킹 도입

집합 원소의 개수가 적을 때, 비트마스크를 통한 집합의 원소 삭제, 추가, 집합끼리의 계산 등의 연산을 효율적으로 수행할 수 있음

알파벳 소문자 26개만을 원소로 가지므로, 이에 적합

 

- 비트마스크 연산

https://loosie.tistory.com/238

[알고리즘] 비트(Bit)와 비트마스크(BitMask) 정리 (Java)

 

 

문자열 abcd를 1111(2)=15(10)

문자열 e를 10000(2)=16(10)

이와 같이 변환하면

 

문장 "abcd e" (문자열 abcd, e의 합집합)

1111 | 10000 = 11111

이처럼 연산할 수 있다(시간복잡도 O(1))

 

위의 방식을 통하여 어떤 문장에 소문자 알파벳 모두가 포함되어있는지 여부를 판단할 수 있음

 

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
	public static final int MAX_SENTENCE = (1 << 26) - 1;
	public static int countOfsentences = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int countOfWords = Integer.valueOf(br.readLine());
		ArrayList<Word> words = new ArrayList<>();
		for (int i = 0; i < countOfWords; i++) {
			String input = br.readLine();
			words.add(new Word(input, convertToBits(input)));
		}
		countViaDfs(words, 0, 0);
		System.out.println(countOfsentences);
	}

	private static void countViaDfs(ArrayList<Word> words, int currSentence, int idx) {
		if (idx == words.size())
			return;
		//포함x
		countViaDfs(words, currSentence, idx + 1);

		//포함o
		int newSentence = currSentence | words.get(idx).converted;
		if (newSentence == MAX_SENTENCE) {
			countOfsentences += 1 << (words.size() - (idx + 1));
		} else {
			countViaDfs(words, newSentence, idx + 1);
		}
	}

	private static int convertToBits(String s) {
		int bitsSentence = 0;
		for (int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			bitsSentence |= 1 << (c - 'a');
		}
		return bitsSentence;
	}
}

class Word {
	String origin;
	int converted;

	public Word(String origin, int converted) {
		this.origin = origin;
		this.converted = converted;
	}
}