[백준 9997번] 폰트

문제 링크: 9997번 폰트

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

 

알고리즘 선택 과정에서의 고민

완전탐색을 해야할 것이라고 생각하지 못하고 효율적인 방법을 고민하느라 많은 시간을 소요했다. 고민하다가 답이 나오지 않을 때는 케이스의 개수나 단어의 길이를 보고 완전탐색도 적극적으로 고민해보아야겠다.

 

구현 과정에서의 고민

원래는 비트마스크를 쓰는 문제인 것 같다... 제시되어 있는 기준에 대해서는 메모리 초과를 했지만 자바라서 채점 기준이 완화되어 있는 것 같다.

단어를 입력받으면, 예를 들어 'ac'라는 단어는 [true, false, true, false, false, false, ...]와 같은 배열로 저장된다. 2차원 boolean 배열 words는 cases개의 단어에 대한, 이러한 boolean 배열을 저장한다. 그리고 각각의 조합에 대해 모든 알파벳이 사용되었는지를 확인한다. alphas의 모든 원소가 true가 되면, 모든 알파벳이 사용된 것이다. 다만 조합을 검사하는 도중에 alphas의 모든 원소가 true가 되면, 남은 문장들은 포함되든 포함되지 않든 무조건 모든 알파벳은 사용된 경우이므로, answer에 2^(남은 문장의 수)를 더해주고 해당 조합은 검사를 중단한다.

 

import java.util.Scanner;
import java.lang.Math;

public class Main {
    static int answer = 0;
    static int numAlphas = (int)('z'-'a')+1; // 알파벳 개수
    static boolean[] alphas;

    public static void check(boolean[][] words, int start) {
        /* 1. 이미 확인하면서 왔는데도, 마지막 단어를 넘었다면 불가능한 조합이다. */
        if (start == words.length) return;

        /* 2. 마지막이 아닐 때, words[start]를 포함하는 경우와 포함하지 않는 경우를 고려한다. */
        // alphas의 값을 저장해두기
        boolean[] origin = alphas.clone();

        /* 2-1. words[start]를 포함하는 경우 */
        boolean flag = true; // 알파벳 하나라도 아직 사용되지 않았으면 false
        for (int i = 0; i < numAlphas; i++) {
            alphas[i] = (alphas[i]) || (words[start][i]);
            if (!alphas[i]) flag = false;
        }

        // 10개(0~9) 중 start = 7째에 모든 알파벳이 사용되었다면, 뒤의 2개 문장은 포함되든 안 되든 가능한 조합이다.
        if (flag)
            answer += Math.pow(2, words.length - start - 1);
        else
            check(words, start + 1);

        /* 2-2. words[start]를 포함하지 않는 경우 */
        // alphas의 값을 되돌리기
        alphas = origin.clone();
        check(words, start+1);
    }

    public static void main(String[] args) {
        /* words to array */
        Scanner sc = new Scanner(System.in);
        int cases = sc.nextInt();

        // alphas는 알파벳이 사용되면 true, 사용되지 않았으면 false를 저장
        alphas = new boolean[numAlphas]; // 자동으로 false로 초기화됨

        // words는 cases개의 단어를 저장
        // words[i]는 각 단어에 대해 알파벳이 사용됐는지의 boolean 배열을 저장
        boolean[][] words = new boolean[cases][];

        for (int i = 0; i < cases; i++) { // 하나의 word에 대해서
            String word = sc.next();
            boolean[] temp = new boolean[numAlphas];

            for (int j = 0; j < word.length(); j++) {
                char current = word.charAt(j);
                temp[(int)(current-'a')] = true;
            }
            words[i] = temp;
        }

        /* check */
        check(words, 0);
        System.out.println(answer);
        sc.close();
    }
}