<Backjoon> #9997 폰트_Brute Force, Recursion, BitMask java

Google 아니고 Joogle·2022년 8월 8일
0

Baekjoon

목록 보기
44/47

#9997 폰트

문제

  • 문제는 단순히 단어를 몇 개 선택하여 문장을 만들었을 때, 이 문장 안에 a~z까지 모든 알파벳을 포함하고 있는지 확인하고 이런 문장이 몇 개 있는지를 출력하는 문제이다

Solution 1 (시간 초과)

  • 현재까지 나온 알파벳의 개수를 저장하는 배열 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--;
	}
	
}

Solution 2

  • 알파벳을 저장하는 배열을 따로 선언하지 않고 비트마스크를 사용하여 관리한다
  • 아래와 같이 26자리의 비트마스크인 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);
	}
}

결론

비트 마스크를 잘 사용 안 했기 때문에 시간 초과 문제를 해결하지 못하고 다른 사람 풀이를 참고했다
비트 마스크를 이용한 문제를 더 풀어보자

profile
Backend 개발자 지망생

0개의 댓글