[Gold IV] 가르침 - 1062 (Java)

문제 요약

남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.

남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.

---

문제 분석

입력받는 단어에 고정적으로 들어가는 알파벳들과 문자열을 전처리해준다.

그 후 비트마스킹을 거친 값을 words배열에 저장해준다.

조합을 통해 사용된 알파벳들을 탐색하며 읽을 수 있는 단어들의 값을 갱신해준다.

---

코드

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

public class Main {
    static int N,K, result;
    // 기본적으로 알아야 하는 글자들
    static final String baseAlphabetes = "antic";
    static final int baseWordBit = 532741;
    // 입력 받은 단어들(비트마스킹을 위해 int 사용)
    static int[] words;
    static List<Character> usedAlphabets;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        // 모든 단어 앞 뒤에 들어가는 anta, tica에 해당하는 글자들의 집합인 baseAlphabete
        // 이보다 적은 수의 K개가 들어오면 기본 단어들도 읽을 수 없기 때문에 무조건 0이다.
        if (K < baseAlphabetes.length()) {
            System.out.println("0");
            return;
        }
        // 전체 알파벳을 알면 모든 단어를 읽을 수 있다.
        if (K == 26) {
            System.out.println(N);
            return;
        }
        words = new int[N];
        usedAlphabets = new ArrayList<>();
        String inputWord = "";
        for (int i = 0; i < N; i++) {
            inputWord = br.readLine();
            // 기본으로 들어가는 글자들인 anta, tica를 제거한 나머지 문자를 저장한다.
            inputWord = inputWord.substring(4, inputWord.length() - 4);
            // 입력된 데이터로 비트마스킹 한 값을 저장.
            for (char c : inputWord.toCharArray()) {
                if(!isBaseAlphabet(c)){
                    words[i] |= makeChatToBit(c);
                    if (!usedAlphabets.contains(c)) {
                        usedAlphabets.add(c);
                    }
                }
            }
        }
        // 만약 선택된 알파벳들의 개수가 K-5개보다 적으면 모든 문자들을 읽을 수 있다.
        if (usedAlphabets.size() < K-5) {
            System.out.println(N);
            return;
        }
        result = 0;
        dfs(0, 5, 0);
        System.out.println(result);
    }
    private static void dfs(int index, int cnt, int selected){
        // 종료조건
        if(cnt == K){
            int readableWords = 0;
            for(int word : words){
                if((selected & word) == word){
                    readableWords++;
                }
            }
            result = Math.max(result, readableWords);
            return;
        }
        if(index == usedAlphabets.size())
            return;
        // 본문
        // 현재 알파벳을 선택하지 않을경우
        dfs(index + 1, cnt, selected);
        // 현재 알파벳을 선택할 경우
        dfs(index + 1, cnt + 1, selected | makeChatToBit(usedAlphabets.get(index)));
    }

    // 현재 char값이 기본문자열인 "antic"에 포함되는지 확인.
    private static boolean isBaseAlphabet(char c){
        int cBit = makeChatToBit(c);
        return (baseWordBit & cBit) == cBit;
//        return baseAlphabetes.indexOf(c) >= 0;
    }
    // char를 비트마스킹 된 bit값으로 변환해준다.
    private static int makeChatToBit(char c){
        return 1 << (c - 'a');
    }
}

---

정리

개선할 점

비트마스킹을 사용해봤지만 까먹어서 고생했었음

사용된 알파벳만 탐색할때 종료조건을 어떻게해야할지 정하는데 시간이 걸림.

---