[Java] 백준 9997. 폰트

📌 문제 링크 - https://www.acmicpc.net/problem/9997

 

 

---

 

 

 

 

 

문제

상근이는 자신이 만든 폰트를 테스트하기 위한 문장을 만들려고 한다. 폰트에는 알파벳 소문자만 포함되어 있기 때문에, 문장은 알파벳 소문자로 작성해야 한다.

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

사실 문제를 많이 풀어본 사람이라면, 문제를 여기까지 읽어도 무슨 문제인지 감이 잡혀야 한다.

상근이는 단어 N개가 포함되어 있는 사전을 하나 가지고 있다. 테스트 문장은 사전에 포함된 단어만 이용해서 만들 수 있으며, 각 단어는 한 번씩만 사용해야 한다. 또, 단어의 순서는 중요하지 않다.

(“uvijek jedem sarmu” 와 “jedem sarmu uvijek”는 같은 문장이다)

상근이가 만들 수 있는 테스트 문장의 개수를 구하는 프로그램을 작성하시오.

 

 

 

입력

첫째 줄에 단어의 개수 N (1 ≤ N ≤ 25)가 주어진다. 다음 N개 줄에는 사전에 포함되어있는 단어가 주어진다. 단어의 길이는 100을 넘지 않으며, 중복되는 단어는 주어지지 않는다.

 

 

 

출력

상근이가 만들 수 있는 테스트 문장의 개수를 출력한다. 

 

 

 

 

---

 

 

풀이

비트마스킹이랑 조합으로 풀 수 있는 문제다.

 

        words = new int[N]; // 단어 사전

        for(int i=0; i<N; i++) {
            char[] tmp = br.readLine().toCharArray();

            for(char c : tmp) {
                words[i] |= 1 << (c - 'a');
            }

            alphabet |= words[i];
        }

먼저, 단어 사전의 단어들을 포함된 알파벳을 비트로 변환해서 정수 배열 words에 저장한다. 

예를 들어 단어가 abc라면 111 => 7로 저장해준다. 

 

마찬가지로 사전에 있는 단어들을 사용하여 알파벳 26개를 전부 포함할 수 있는지 확인하기 위해 정수 변수 alphabet에 모든 단어의 비트마스크를 OR 연산으로 누적하여 포함된 알파벳을 계산해준다.

 

 

    private static void comb(int idx, int result) {
        if(result == COMPLETED) {
            total += 1 << (N - idx);
            return;
        }
        if(idx == N) return;

        comb(idx + 1, result);
        comb(idx + 1, result | words[idx]);
    }//comb

이후 알파벳들을 모두 사용할 수 있다면 조합을 통해 만들 수 있는 문장 개수를 구해주면 된다. 

이때 기저조건으로는 아래의 2가지 조건을 확인한다.

• 현재 조합이 알파벳 26개를 전부 포함했는지 (result == COMPLETED)
• 모든 단어를 확인 했는지 (idx == N)

 

현재 조합이 알파벳 26개를 모두 포함했다면 남은 단어들로 만들 수 있는 모든 조합을 총 개수에 더해주고, 

모든 단어를 확인했다면 탐색을 종료한다.

 

 

---

 

 

코드

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

// https://www.acmicpc.net/problem/9997
public class Main_9997 {
    private static final int CNT = 26; // 알파벳 26개
    private static final int COMPLETED = (1 << CNT) - 1; // 알파벳 모두 포함
    private static int N; // 단어 개수
    private static int alphabet; // 사전에 포함된 알파벳 개수
    private static int total; // 만들 수 있는 테스트 문장의 개수
    private static int[] words; // 단어 사전


    public static void main(String[] args) throws IOException {
        init();

        // 테스트 문장 만들 수 있음
        if(alphabet == COMPLETED) {
            comb(0, 0);
        }

        System.out.print(total);
    }//main


    private static void comb(int idx, int result) {
        if(result == COMPLETED) {
            total += 1 << (N - idx);
            return;
        }
        if(idx == N) return;

        comb(idx + 1, result);
        comb(idx + 1, result | words[idx]);
    }//comb


    private static void init() 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++) {
            char[] tmp = br.readLine().toCharArray();

            for(char c : tmp) {
                words[i] |= 1 << (c - 'a');
            }

            alphabet |= words[i];
        }

        br.close();
    }//init


}//class